luogu 4158 粉刷匠 dp套dp

时间：2023-03-09 16:24:42
luogu 4158 粉刷匠 dp套dp

dp套dp

每个木板是个递推的dp,外部是个分组背包

#include<bits/stdc++.h>

#define rep(i,x,y) for(register int i=x;i<=y;i++)

using namespace std;

const int N=;

const int T=;

inline int read(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;}

int n,m,t,f[N][N],dp[N][T],s[N];char s1[N];

int main(){

    n=read();m=read();t=read();

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

        memset(f,,sizeof f);

        memset(s,,sizeof s);

        scanf("%s",s1+);

        for(int j=;j<=m;j++) s[j]=s[j-]+(s1[j]=='');

        //提前预处理字符串贡献，利用前缀和

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

        for(int k=;k<=m;k++)// i,j代表前i个字母刷了j个

        for(int z=;z<j;z++){

            int dis=s[j]-s[z];

            f[j][k]=max(f[j][k],f[z][k-]+max(dis,j-z-dis));

            // f[j][k] 代表本行中前j格涂了k次的最大收益

        }

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

            int top=min(j,m);

            //防止出现实际上不存在的格子

            for(int k=;k<=top;k++)

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

            // 就算本条木板中有些不涂，向后递推，答案也不会变得更劣，所以每行的最优答案集中在f[m]上

    }int ans=;// dp i,j分别代表前i行涂了j个格子的情况

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

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

}

相关文章