bzoj1296: [SCOI2009]粉刷匠（DP）

时间：2022-02-12 11:05:31

1296: [SCOI2009]粉刷匠

题目：传送门

题解：

　　 DP新姿势：dp套dp

　　 我们先单独处理每个串，然后再放到全局更新：

　　 f[i][k]表示当前串枚举到第i个位置，用了k次机会

　　 F[i][j]则表示总答案

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int n,m,t;

 int f[][];

 int F[][];

 char st[];int a[];

 int main()

 {

     scanf("%d%d%d",&n,&m,&t);getchar();

     memset(F,,sizeof(F));

     for(int i=;i<=n;i++)

     {

         scanf("%s",st+);

         a[]=;for(int j=;j<=m;j++)a[j]=a[j-]+st[j]-'';

         memset(f,,sizeof(f));

         for(int j=;j<=m;j++)

             for(int k=;k<=min(j,t);k++)

                 for(int l=;l<=j;l++)

                 {

                     int s=a[j]-a[l-];

                     f[j][k]=max(f[j][k],f[l-][k-]+max(s,(j-l+)-s));

                 }

         for(int j=;j<=t;j++)

             for(int k=;k<=min(m,j);k++)

                 F[i][j]=max(F[i][j],F[i-][j-k]+f[m][k]);

     }

     int ans=1e-;

     for(int i=;i<=t;i++)ans=max(ans,F[n][i]);

     printf("%d\n",ans);

     return ;

 }

相关文章