Codeforces 351C Jeff and Brackets 矩阵优化DP

约定不等于承诺〃 2021-12-12 02:01 272阅读 0赞

题意：你要在纸上画一个长度为n \* m的括号序列，第i个位置画左括号的花费是a\[i % n\], 画右括号的花费是b\[i % n\]，问画完这个括号序列的最小花费。n <= 20, m <= 1e7

思路：如果不管n和m的限制，这个题很好做，设dp\[i\]\[j\]是到i位置，平衡因子是j的花费，dp\[i\]\[j\] = min(dp\[i - 1\]\[j - 1\] + a\[i\], dp\[i - 1\]\[j + 1\] + b\[i\])，但是这样n \* m到2e8级别，这是我们无法承受的。不过，我们可以发现一个性质：平衡因子的大小不会超过2 \* n,因为如果超过2 \* n,我们可以通过交换顺序而不改变答案，让平衡因子都小于2 \* n。我们想一下dp的转移，我们发现可以用一次矩阵乘法来执行一次转移(设转移矩阵是C)，那么C\[j\]\[j + 1\] = a\[i\]，C\[j\]\[j - 1\] = b\[i\]，那么乘一次这个矩阵就执行了一次转移，因为a和b数组是长度为n的循环，那么我们可以一次处理出n次转移的矩阵（由矩阵乘法的结合律可知），再用矩阵快速幂执行这样的n次转移m次，就得到了最终的答案。

代码：

#include <bits/stdc++.h>
    #define INF 2e9
    #define LL long long
    using namespace std;
    int a[30], b[30], N;
    struct Matrix {
    	LL a[55][55];
    	Matrix(int x = INF) {
    		memset(a, 0x3f, sizeof(a));
    		for (int i = 0; i < N; i++)
    			a[i][i] = x;
    	}
    	friend Matrix operator * (const Matrix& A, const Matrix& B) {
    		Matrix ans;
    		for (int i = 0; i < N; i++)
    			for (int j = 0; j < N; j++)
    				for (int k = 0; k < N; k++)
    					ans[i][j] = min(ans[i][j], A[i][k] + B[k][j]);
    		return ans;
    	}
    	Matrix operator ^ (int y) {
    		Matrix x = *this, ans(0);
    		for (; y; y >>= 1) {
    			if(y & 1) ans = ans * x;
    			x = x * x;
    		}
    		return ans;
    	}
    	LL*operator [](int x) {
    		return a[x];
    	}
    	const LL*operator [](int x) const {
    		return a[x];
    	}
    };
    
    int main() {
    	int n, m;
    	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= n; i++)
    		scanf("%d", &a[i]);
    	for (int i = 1; i <= n; i++)
    		scanf("%d", &b[i]);
    	N = 2 * n + 1;
    	Matrix dp, A(0);
    	dp[0][0] = 0;
    	for (int i = 1; i <= n; i++) {
    		Matrix tmp;
    		for (int j = 0; j <= N; j++) {
    			if(j) tmp[j - 1][j] = a[i];
    			if(j < 2 * n) tmp[j + 1][j] = b[i];
    		}
    		A = A * tmp;
    	}
    	dp = dp * (A ^ m);
    	printf("%lld\n", dp[0][0]);
    }

转载于:https://www.cnblogs.com/pkgunboat/p/10990308.html