【[SCOI2009]粉刷匠】

这好像是个暴力?

但是跑的挺快的

我们设\(dp[i][j][k]\)表示在第\(i\)行我们最远染到的位置是\(j\)，这一行上一共染了\(k\)次最多能染对多少个格子

理性分析一下啊，每一行最多也就染\(m\)次，这样就能把这一行格子全部都染对

所以这个空间复杂度是\(nm^2\)的

之后考虑一下转移

显然这就是一个非常经典的断点\(dp\)了，转移为

\[dp[i][j][k]=max(dp[i][p][k-1]+max(s_0[p+1,j],s_1[p+1,j]))
\]

\(s_0[p+1,j]\)表示这个区间内有几个\(0\)，后面那个也就是我们能够正确覆盖的格子数量

最后用分组背包合并大案就好了

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#define max(a,b) ((a)>(b)?(a):(b))

#define re register

int dp[51][51][51];

int pre[51][51][2];

char S[51][51];

int f[2501];

int n,m,T;

int main()

{

    scanf("%d%d%d",&n,&m,&T);

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

    {

        scanf("%s",S[i]+1);

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

        if(S[i][j]=='1') pre[i][j][1]=pre[i][j-1][1]+1,pre[i][j][0]=pre[i][j-1][0];

            else pre[i][j][1]=pre[i][j-1][1],pre[i][j][0]=pre[i][j-1][0]+1;

    }

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

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

            for(re int k=1;k<=j;k++)

                for(re int p=0;p<j;p++)

                    dp[i][j][k]=max(dp[i][j][k],dp[i][p][k-1]+max(pre[i][j][0]-pre[i][p][0],pre[i][j][1]-pre[i][p][1]));

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

        for(re int j=T;j>=0;j--)

            for(re int k=0;k<=m;k++)

                if(j-k>=0) f[j]=max(f[j],f[j-k]+dp[i][m][k]);

    printf("%d\n",f[T]);

    return 0;

}

巴特西

【[SCOI2009]粉刷匠】

最新文章

热门文章