15年市选的T2原题哟=v=。。。不过我当时以为能竖着画就一直想不出啊QAQAQAQAQ
好吧对每个木板：a[i][0/1]为前缀和，d[i][j]为画i次长度为j的正确粉刷的格子数
所以d[j][k]=max(d[j][k],d[j-1][v]+max(a[k][1]-a[v][1],a[k][0]-a[v][0]))
得出c[i][j]（第i个木板用j时间正确粉刷的格子数）然后背包问题就出来了。。。
4层循环有点恶心。。。但数据弱的话就乱搞乱搞乱搞啦。。。
1 #include<bits/stdc++.h> 2 #define inc(i,l,r) for(i=l;i<=r;i++) 3 #define dec(i,l,r) for(i=l;i>=r;i--) 4 #define inf 1e9 5 #define NM 60 6 #define mem(a) memset(a,0,sizeof(a)) 7 using namespace std; 8 int a[NM][2],d[NM][NM],c[NM][NM],ans[3000],i,n,m,p,k,v,j,s,tmp[3000]; 9 char x[NM][NM]; 10 int main(){ 11 scanf("%d%d%d",&n,&m,&p); 12 inc(i,1,n) 13 scanf("%s",x[i]); 14 inc(i,1,n){ 15 mem(a);mem(d); 16 inc(j,1,m){ 17 a[j][1]=a[j-1][1];a[j][0]=a[j-1][0]; 18 if(x[i][j-1]==‘1‘)a[j][1]++;else a[j][0]++; 19 } 20 inc(j,1,m) 21 inc(k,1,m) 22 inc(v,0,k-1) 23 d[j][k]=max(d[j][k],d[j-1][v]+max(a[k][1]-a[v][1],a[k][0]-a[v][0])); 24 inc(j,1,m)c[i][j]=d[j][m]; 25 } 26 inc(i,1,n){ 27 inc(j,1,m) 28 dec(k,p,j) 29 ans[k]=max(ans[k],tmp[k-j]+c[i][j]); 30 inc(j,1,p)tmp[j]=ans[j]; 31 } 32 inc(i,1,p) 33 s=max(s,ans[i]); 34 printf("%d",s); 35 return 0; 36 37 }
原文：http://www.cnblogs.com/onlyRP/p/4722711.html
