对于每一行做DP预处理，w[i][j]代表这一行前i个刷j次的最大价值，那么w[i][j]=max(w[i][j],w[k][j-1]+sum[k+1][i])，sum[i][j]为i-j段刷一次最多正确刷多少个。
那么我们可以将每一行看做一个物品，对于整体做DP，W[i][j]代表前i行刷j次的最大价值，那么W[i][j]=max(W[i][j],W[i-1][j-k]+w[i][k])k<m，这样就可以了。
反思：枚举k的时候方程写错了，写成W[i-1][k]+w[i][j-k]了。
/************************************************************** Problem: 1296 User: BLADEVIL Language: C++ Result: Accepted Time:120 ms Memory:1564 kb****************************************************************/ //By BLADEVIL#include#include #include #define maxn 60#define maxk 3000 using namespace std; int n,m,t,ans;int map[maxn][maxn],w[maxn][maxn],sum[maxn][maxn],W[maxn][maxn],ww[maxn][maxk];char s[maxn]; int work(int x) { memset(w,0,sizeof w); memset(sum,0,sizeof sum); for (int i=1;i<=m;i++) for (int j=i;j<=m;j++) for (int k=i;k<=j;k++) if (map[x][k]) sum[i][j]++; for (int i=1;i<=m;i++) for (int j=i;j<=m;j++) sum[i][j]=max(sum[i][j],j-i+1-sum[i][j]);//printf("%d %d %d\n",i,j,sum[i][j]); for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) { w[j][i]=w[j-1][i]; for (int k=0;k