BZOJ 1296 [SCOI2009]粉刷匠 - DP

一开始看错数据范围，搞了一个 O(Tn2m2) 的，然后就GG了。

这种做法的思路是，枚举当前状态，可以继续涂此层剩余，也可以涂他层，一分类讨论即可。

后来发现这种做法肯定有大量重复，而且每行之间独立，不必将每行的状态混在一起，于是每行dp搞用cost最多的得分，然后行与行之间分组dp就好了。

TLE：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=;
const int maxt=;

int n,m,t;
char s[maxn][maxn];
int sum[maxn][maxn];
int dp[maxt][maxn][maxn];

inline int getans(int x,int l,int r)
{
    return max(sum[x][r]-sum[x][l-],r-l+-(sum[x][r]-sum[x][l-]));
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=;i<=n;i++)
        scanf("%s",s[i]+);
//初始化 
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
            sum[i][j]=sum[i][j-]+(s[i][j]=='0');
    for(int i=;i<=n;i++)
        for(int k=;k<=m;k++)dp[][i][k]=getans(i,,k);

    for(int i=;i<=t;i++)
    {
        for(int j=;j<=n;j++)//层数
        {
            for(int k=;k<=m;k++)//个数 
            {
                //本层状态 
                for(int l=k+;l<=m;l++)
                    dp[i][j][l]=max(dp[i][j][l],dp[i-][j][k]+getans(j,k+,l));
                //别层状态
                for(int l=j+;l<=n;l++)
                    for(int p=;p<=m;p++)
                        dp[i][l][p]=max(dp[i][l][p],dp[i-][j][k]+getans(l,,p));
            }
        }
    }
    int ans=;
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
            ans=max(ans,dp[t][i][j]);
    printf("%d",ans);
}
           

AC:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;

const int maxn=;
const int maxt=;

int n,m,t;
char s[maxn][maxn];
int sum[maxn][maxn];
int dp[maxn][maxt],f[maxn][maxn][maxn];

inline int getans(int x,int l,int r)
{
    return max(sum[x][r]-sum[x][l-],r-l+-(sum[x][r]-sum[x][l-]));
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=;i<=n;i++)
        scanf("%s",s[i]+);
//初始化 
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
            sum[i][j]=sum[i][j-]+(s[i][j]=='0');
//每层独立dp 
    for(int i=;i<=n;i++)//层数 
    {
        for(int l=;l<=m;l++)
            f[i][][l]=getans(i,,l);
        for(int j=;j<=m;j++)//次数 
            for(int k=j-;k<=m;k++)//上次结尾
                for(int l=k+;l<=m;l++)//本次结尾 
                    f[i][j][l]=max(f[i][j][l],f[i][j-][k]+getans(i,k+,l));
    }
    /*for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
            printf("%d%c",f[1][i][j],j==m?'\n':' '); */
//分组背包dp 
    for(int i=;i<=n;i++)//层数 
        for(int j=;j<=t;j++)//上次剩余 
            for(int k=;k<=min(m,j);k++)//本次使用 
                dp[i][j-k]=max(dp[i][j-k],dp[i-][j]+f[i][k][m]);
    printf("%d",dp[n][]);
    return ;
}