BZOJ 1296: [SCOI2009]粉刷匠 分组DP

时间：2021-10-27 15:17:17

1296: [SCOI2009]粉刷匠

Description

windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

Input

输入文件paint.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。

Output

输出文件paint.out包含一个整数，最多能正确粉刷的格子数。

Sample Input

3 6 3
111111
000000
001100

Sample Output

16

HINT

30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。
100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。

题解：PoPoQQQ

给定n*m的木板，每个点需要刷成1和0两种颜色之一，每次只能刷一行中连续的一段，一个点只能刷一次，求T刷子最多能刷对多少个点

首先对每行拆开处理 令f[i][j]为用i刷子刷前j个格子最多刷对多少个点 动规处理出这一行刷i刷子最多能刷对多少个点 然后分组背包即可

//meek

///#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define pb push_back

#define fi first

#define se second

#define MP make_pair

const int N=;

const ll INF = 1ll<<;

const int inf = <<;

const int mod= ;

const int M = ;

char s[N];

int f[N][N],n,m,K,a[N][N];

void DP(int pos) {

   memset(f,,sizeof(f));

  f[][] = ;

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

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

            int cnt[] = {};

        for(int k=j;k>=i;k--) {

            cnt[s[k]-''] ++;

            f[i][j] = max(f[i][j],f[i-][k-]+max(cnt[],cnt[]));

        }

    }

  }

  for(int i = ;i <= m; i++) a[pos][i] = f[i][m];

}

int fenzu() {

  int g[N][N*N];

  memset(g,,sizeof(g));

  g[][] = ;

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

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

        for(int k=K;k>=j;k--) g[i][k] = max(g[i][k],g[i-][k-j]+a[i][j]);

    }

  }

    return g[n][K];

}

int main() {

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

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

       scanf("%s",s+);

       DP(i);

    }

    printf("%d\n",fenzu());

    return ;

}

代码

相关文章