[BZOJ1296][SCOI]粉刷匠

原题地址

刷水…

数组开小了一次，呵呵…

#include <cstdio>#include <algorithm>using namespace std;const int N=55;const int M=2510;int n,m,T,ans;int s1[N][N],s2[N][N],g[N][M];int f[N][N][N];int main(){scanf("%d%d%d",&n,&m,&T);T=min(T,n*m);for(int i=1;i<=n;i++){char t[N];scanf("%s",t);for(int j=1;j<=m;j++){s1[i][j]=s1[i][j-1]+(t[j-1]=='0');s2[i][j]=s2[i][j-1]+(t[j-1]=='1');}}for(int i=1;i<=n;i++){f[i][1][1]=1;for(int j=1;j<=m;j++){for(int k=1;k<=j;k++){for(int jj=k-1;jj<j;jj++){int mx=max(s1[i][j]-s1[i][jj],s2[i][j]-s2[i][jj]);f[i][j][k]=max(f[i][j][k],f[i][jj][k-1]+mx);}}}}for(int i=1;i<=m&&i<=T;i++) g[1][i]=f[1][m][i];for(int i=2;i<=n;i++)for(int j=0;j<=i*m&&j<=T;j++)for(int k=0;k<=m&&k<=j;k++)g[i][j]=max(g[i][j],g[i-1][j-k]+f[i][m][k]);for(int i=1;i<=T;i++) ans=max(ans,g[n][i]);printf("%d\n",ans);return 0;}