这题很强，get到新姿势dp套dp。

f[j][k]表示第i个串，枚举到第j个位置涂了k次的最优解。

那么O(n^3)搞定。

然后我挂在背包了。。。

就是拿dp完的值去背包。好像不能直接空间T的背包，要每个串记录转移，原因不明。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int f[60][60],b[60][3100];char ss[110];int s[110];int main(){ freopen("paint.in","r",stdin); freopen("paint.out","w",stdout); int n,m,T; scanf("%d%d%d",&n,&m,&T); memset(b,0,sizeof(b)); for(int i=1;i<=n;i++) { scanf("%s",ss+1); s[0]=0;for(int j=1;j<=m;j++)s[j]=s[j-1]+(ss[j]-'0'); memset(f,0,sizeof(f)); for(int j=1;j<=m;j++) for(int k=1;k<=min(T,j);k++) for(int jj=1;jj<=j;jj++) { int d=s[j]-s[jj-1]; f[j][k]=max(f[j][k],f[jj-1][k-1]+max(d,(j-jj+1)-d)); } for(int j=1;j<=T;j++) { for(int k=1;k<=min(m,j);k++) b[i][j]=max(b[i][j],b[i-1][j-k]+f[m][k]); } } int ans=0; for(int i=1;i<=T;i++)ans=max(ans,b[n][i]); printf("%d\n",ans); return 0;}