Description

windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
Input

输入文件paint.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，’0’表示红色，’1’表示蓝色。
Output

输出文件paint.out包含一个整数，最多能正确粉刷的格子数。
Sample Input
3 6 3

111111

000000

001100

Sample Output
16

HINT

30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。 100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。

解法：

首先对每行拆开处理 令dp[i][j]为用i刷子刷前j个格子最多刷对多少个点 动规处理出这一行刷i刷子最多能刷对多少个点

然后分组背包即可，DP好难，我这种弱智选手打出GG了。

//BZOJ 1296 DP

#include <bits/stdc++.h>
using namespace std;
int n, m, T, dp[60][60];
///dp[i][j]表示用i刷子刷前j个格子能刷出的最多格子
///dp[i][j] = max(dp[i-1][k]+max(cnt[0], cnt[1]))

int a[60][60];
char s[60];

int dp2[60][60*60]; ///dp2[i][j]代表用了前个串，容量为j可以得到的最大值

///a[i][j]表示用第i行用j刷子可以刷出的最大值

void DP(int x){
 memset(dp, 0xef, sizeof(dp));
 dp[0][0]=0;
 for(int i=1; i<=m; i++){
 for(int j=i; j<=m; j++){
 int cnt[2]={0};
 for(int k=j-1; k>=i-1; k--){
 cnt[s[k+1]-'0']++;
 dp[i][j] = max(dp[i][j], dp[i-1][k]+max(cnt[0], cnt[1]));
 }
 }
 }
 for(int i=1; i<=m; i++) a[x][i] = dp[i][m];
}

void work(){
 memset(dp2, 0xef, sizeof(dp2));
 dp2[0][0]=0;
 for(int i=1; i<=n; i++){
 for(int j=0; j<=m; j++){
 for(int k=T; k>=j; k--)
 dp2[i][k] = max(dp2[i][k], dp2[i-1][k-j] + a[i][j]);
 }
 }
 printf("%d\n", dp2[n][T]);
}

int main(){
 scanf("%d%d%d", &n,&m,&T);
 for(int i=1; i<=n; i++){
 scanf("%s", s+1);
 DP(i);
 }
 work();
 return 0;
}