SCOI2009 粉刷匠

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2009 粉刷匠

Date: Thu Sep 06 09:18:13 CST 2018

In Category: NoCategory

Description：

有 $ N $ 条木板。每条木板有 $ M $ 个格子要被刷成红色或蓝色。每次粉刷只能选择一条木板上一段格子涂上一种颜色。问粉刷 $ T $ 次最多能正确粉刷多少格子。

$1\le n,m\le 50,1\le T \le 2500$

Solution：

先 $O(nm^2T)$ 暴力 $DP$ 出 $g[i][j]$ 表示当前这块木板前 $i$ 个格子粉刷了 $j$ 次，转移时枚举粉刷的左边界转移，前缀和计算价值，然后对每行跑分组背包。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,t;

#define MAXN 51

int s[MAXN][MAXN];

inline int geti()

{

    register char c = getchar();

    while(c != '0' && c != '1')c = getchar();

    return c - '0';

}

#define MAXT 2510

int f[MAXT];

int g[MAXN][MAXT];

int main()

{

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

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

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

            s[i][j] = s[i][j - 1] + geti();

    for(int w = 1;w <= n;++w)

    {

        memset(g,0,sizeof(g));

        for(int i = 1;i <= m;++i)

        {

            for(int k = 1;k <= t;++k)

            {

                g[i][k] = g[i - 1][k];

                for(int j = 0;j < i;++j)

                {

                    g[i][k] = max(g[i][k],g[j][k - 1] + max(s[w][i] - s[w][j],(i - j) - (s[w][i] - s[w][j])));

                }

            }

        }

        for(int j = t;j >= 0;--j)

        {

            for(int i = 0;i <= j;++i)

            {

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

            }

        }

    }

    cout << f[t] << endl;

    return 0;

}

In tag: DP-DP DP-背包

wjh15101051