bzoj1296 [SCOI2009]粉刷匠

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

HINT

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

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

正解：划分型$dp$+背包。

比较简单的一个题。我们可以发现，每个串涂$k$次可以涂对几个可以用划分型$dp$来做。然后我们用多重背包，把所有串合并一下就行了。

然而我因为数组开小调了好久。。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define inf (1<<30)
14 #define il inline
15 #define RG register
16 #define ll long long
17 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
18 
19 using namespace std;
20 
21 int f[60][60],g[60][2600],a[60],n,m,t;
22 
23 il int gi(){
24     RG int x=0,q=1; RG char ch=getchar();
25     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
26     if (ch=='-') q=-1,ch=getchar();
27     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
28     return q*x;
29 }
30 
31 il int gc(){
32     RG char ch=getchar();
33     while (ch!='0' && ch!='1') ch=getchar();
34     return ch=='1';
35 }
36 
37 il void work(){
38     n=gi(),m=gi(),t=gi();
39     for (RG int l=1;l<=n;++l){
40     for (RG int i=1;i<=m;++i){
41         a[i]=a[i-1]+gc();
42         for (RG int k=1;k<=t && k<=m;++k){
43         f[i][k]=f[i-1][k];
44         for (RG int j=0;j<i;++j)
45             f[i][k]=max(f[i][k],f[j][k-1]+max(a[i]-a[j],i-j-a[i]+a[j]));
46         }
47     }
48     for (RG int i=0;i<=t;++i) g[l][i]=g[l-1][i];
49     for (RG int i=1;i<=t && i<=m;++i)
50         for (RG int j=i;j<=t;++j) g[l][j]=max(g[l][j],g[l-1][j-i]+f[m][i]);
51     }
52     printf("%d
",g[n][t]); return;
53 }
54 
55 int main(){
56     File("paint");
57     work();
58     return 0;
59 }