[动态规划][SCOI2009]粉刷匠

题目传送门:https://www.luogu.org/problemnew/show/P4158

----------

####题目描述
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。

windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。

如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

####输入格式：
第一行包含三个整数，N M T。

接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。

####输出格式：
包含一个整数，最多能正确粉刷的格子数。

----------
###题解：
一个矩阵？我们先不考虑多维的情况，先从简单的想起.
当只有一行的时候，我们设定f[i][j]为前i格涂j次能正确涂色的最大格子数.
枚举一个断点k,我们就有:

$f[i][j]=\max(f[k][j-1]+max([k+1,r]))$

其中,max([k+1,r])表示[k+1,r]这个区间中较多的那一种颜色,可以用前缀和O(1)查询。

对于没一个n,我们都算出第n行(一整行！)涂y次能得到的最大正确数,记录在g[n][y];
题目要求最多能够涂T次，那么相当于把这T次分配给每一行，要求最大总和，显然转化为了一个背包模型!
所以，我们再进行一次动态规划,dp[i][j]表示前i行涂j次能获得的最大正确数,我们就有:

$dp[i][j]=max(dp[i-1][j-y]+g[i][y])$

问题就<del>轻松</del>地解决了！！

----------

贴上代码:

代码#include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #include<memory.h>
    #define maxn 100
    #define maxm 5000
    using namespace std;
    int f[maxn][maxm],g[maxn][maxm],dp[maxn][maxm],sum[maxn][maxn];
    int n,m,t;
    int main()
    {
        scanf("%d%d%d",&n,&m,&t);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int t;
                scanf("%1d",&t);
                sum[i][j]=sum[i][j-1]+t;
            }
        }
        for(int r=1;r<=n;r++)
        {
            memset(f,0,sizeof(f));
            for(int k=1;k<=t;k++)
            {
                for(int i=1;i<=m;i++)
                {
                    for(int j=0;j<i;j++)
                    {
                        f[i][k]=max(f[i][k],f[j][k-1]+max(sum[r][i]-sum[r][j],i-j-(sum[r][i]-sum[r][j])));
                    }
                    //printf("%d ",f[i][k]);
                    if(i==m) g[r][k]=f[i][k];
                }
                //printf("\n");
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=t;j>=1;j--)
            {
                for(int y=1;y<=j;y++)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-y]+g[i][y]);
                }
            }
        }
        printf("%d",dp[n][t]);
    }

PhantasmDragon 's Blog