题目描述
有n条独立的木棍,每个木棍有m格,每一格有一个预定的颜色,每次操作可以染一个木棍中连续的段,可以染T次,求最优的染对的个数
算法1
(动态规划) $O(n m^3 + n m T)$
我们可以通过模块化思想来考虑问题
因为这些木棍是独立的,这里我们可以只考虑一根(即n = 1)的情况,这是我们划分的第一步。
我们设 $g_{i,j}$ 为刷到第i格用了j次刷子的最优数(请注意这里第i格是一定被刷到了)
此时我们在脑海中可以假想一个最优方案,由于每个格子只能刷一次,那么粉刷的顺序是无所谓的,于是我们认为最后一次粉刷粉刷到了i格
于是一个状态转移方程呼之欲出:$ g_{i,j} = g_{l, j - 1}+\Delta \\ l < i$
$\Delta$就是指从l + 1 刷到 i 最多能加几个数(可以用前缀和来维护)
进而利用g我们可以得到每根木棍用了几次刷子时的最优数我们设为fi
完成第一步之后,就要考虑n > 1 的情形
这里我们设$f_{i,j,k}为第i根棍子用了j次刷子并且总共用了k次刷子的最优数
于是我们可以简单的得到转移方程:$$f_{i,j,k} = \begin{cases} f_{i, j-1, k-1} + fi_{i, j} - fi_{i, j - 1} & j >= 0,\\
max{f_{i -1, l, k}} & j = 0, l = 1..m.
\end{cases} $
这样就完成了证明,这样想虽然代码写起来多,但是思路清晰也方便调试,个人认为还是不错的
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 55, M = 2505;
int n, m, T;
int a[N][N], b[N][N];
int g[N][N][N], fi[N][N], f[N][N][M];
string s[N];
int main(){
ios::sync_with_stdio(0);
cin >> n >> m >> T;
for(int i = 1; i <= n; ++ i){
cin >> s[i];
//for(int j = m; j >= 1; -- i)s[i][j] = s[i][j - 1];
}
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j){
if(s[i][j - 1] == '0') a[i][j] = a[i][j - 1] + 1, b[i][j] = b[i][j - 1];
else b[i][j] = b[i][j - 1] + 1, a[i][j] = a[i][j - 1];
}
for(int i = 1; i <= n; ++ i)
for(int k = 1; k <= m; ++ k){
if(k == 1){
for(int j = 1; j <= m; ++j) g[i][j][k] = max(a[i][j], b[i][j]);
}else
for(int j = 1; j <= m; ++j)
for(int l = 1; l < j; ++ l)g[i][j][k] = max(g[i][j][k], g[i][l][k - 1] + max(a[i][j] - a[i][l], b[i][j] - b[i][l]));
}
for(int i = 1; i <= n; ++i)
for(int k = 1; k <= m; ++ k)
for(int j = 1; j <= m; ++j)
fi[i][k] = max(fi[i][k], g[i][j][k]);
memset(f, -0x3f, sizeof(f));// cout << f[0][0][0];
for(int i = 0; i <= n; ++ i) f[i][0][0] = 0;
for(int k = 1; k <= T; ++ k){
for(int i = 1; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
if(j == 0) for(int l = 0; l <= m; ++ l) f[i][0][k] = max(f[i][0][k], f[i - 1][l][k]);
else{
f[i][j][k] = f[i][j - 1][k - 1] + fi[i][j] - fi[i][j - 1];
}
}
int ans = 0;
for(int i = 0; i <= m; ++ i) ans = max(ans, f[n][i][T]);
cout << ans << endl;
}