windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
n,m<=50 T<=2500
题解：dp大合集!!!!
h[k][i][j]表示第k个木板刷i到j最多能刷对几个，这个很好处理。
g[k][i][j]表示第k个木板前i个刷j次最多刷对几个 g[k][i][j]=max(g[j][l][j-1]+h[l+1][i]) 这个也很好处理
e[k][i]表示第k个木板刷i次最多能刷对几个，这个就从g里取一个最值就好啦。
f[i][j]表示前i个木板刷j次最多能刷对几个 f[i][j]=max(f[i-1][j-k]+e[i][k]) 这个也很好处理
总复杂度 n^3 + n^4 +n^2T
#include<iostream> #include<cstdio> #include<cstring> #define MAXN 1000000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int h[55][55]; int g[55][55]; int e[55][55]; int f[55][2505]; int n,m,T,num1,num2; char st[55]; int main() { n=read();m=read();T=read(); for(int num=1;num<=n;num++) { scanf("%s",st+1); memset(h,0,sizeof(h)); memset(g,0,sizeof(g)); for(int i=1;i<=m;i++) { num1=num2=0; for(int j=i;j<=m;j++) { if(st[j]=='0')num1++; else num2++; h[i][j]=max(num1,num2); } } for(int k=1;k<=m;k++) for(int i=1;i<=m;i++) for(int j=0;j<i;j++) g[i][k]=max(g[i][k],g[j][k-1]+h[j+1][i]); for(int k=1;k<=m;k++) for(int i=k;i<=m;i++) e[num][k]=max(e[num][k],g[i][k]); } for(int j=1;j<=T;j++) for(int i=1;i<=n;i++) for(int k=1;k<=min(m,j);k++) f[i][j]=max(f[i][j],f[i-1][j-k]+e[i][k]); printf("%d",f[n][T]); return 0; }