【每日一题】粉刷匠 题解

Solution

一看数据范围, 肯定是个 了
但是这个数据范围做不了状压
考虑普通的
这个问题的难点在于他是二维的情况(多个木块)
那么如果是一维的情况怎么做呢?我们先考虑一下
令 表示第 个木板粉刷 次涂了前面 个格子的正确格子数
因为只有两种颜色, 对于某一块木板, 我们可以维护一个前缀和 表示第 个木板的第 个格子前蓝色格子的数目
对于单个木板有
表示对第 块木板涂了 次, 此时到第 个位置可以从第 块木板的涂了 次的第 个位置转移过来
对于要么取蓝色, 要么取红色, 我们取个 即可, 是 的蓝色格子 是 的红色格子
此时再考虑多个木板情况
显然有
表示到第 个木板涂了 次可以从 第个木板涂了 次转移过来

Code

/*
  autor: Kurisu
  2020年4月30日16:48:49
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long inf = 1e18;
const int N = 1e6 + 5;
const double eps = 1e-10;
const ll mod = 23333333333333333;
ll dp[55][2505]; // 前 i 个木板粉刷 j 次的正确格子数
ll f[55][2505][55]; // 第 i 个木板粉刷 j 次涂了前面 k 个格子的正确格子数
ll sum[55][55]; // 第 i 个木板的第 j 个格子前蓝色格子的数目
int main() {
  int n, m, t;
  cin >> n >> m >> t;
  string s;
  for(int i = 1; i <= n; i++) {
    cin >> s;
    s = ' ' + s;
    sum[i][0] = 0;
    for(int j = 1; j <= m; j++) {
      sum[i][j] = sum[i][j - 1] + (s[j] == '1');
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      for(int k = 1; k <= m; k++) {
        for(int l = j - 1; l < k; l++) {
          f[i][j][k] = max(f[i][j][k], f[i][j - 1][l] + max(sum[i][k] - sum[i][l], k - l - sum[i][k] + sum[i][l]));
        }
      }
    }
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= t; j++) {
      for(int k = 0; k <= min(j, m); k++) {
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + f[i][k][m]);
        ans = max(ans, dp[i][j]);
      }
    }
  }
  cout << ans << "\n";
  return 0;
}