BZOJ1296 [SCOI2009]粉刷匠

2015.01.25 18:54 Sun| 1 visits oi_2015| 2015_刷题日常| Text

Solution

两个 DP。首先 f[i][j][k] 表示第 i 行前 j 个字符中粉刷 k 次所能正确粉刷的格子数目。预处理出每一行中红色格子数目的前缀和,对于每一行可以在 $\mathcal O(m^3)$ 的时间内求出答案。之后需要在列上跑一遍背包出解。

特别地,这道题可以将两部分代码实现结合到一起,省去一维空间(当然,我并没有这样做)。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 55
char a[N][N];
int n, m, t, s[N][N], f[N][N][N], ans[N][2505];

int main()
{
  cin >> n >> m >> t;
  for (int i = 1; i <= n; ++i)
    scanf("%s", a[i] + 1);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      s[i][j] = s[i][j-1] + (a[i][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 = 0; l < k; ++l)
          f[i][k][j] = max(f[i][k][j], f[i][l][j-1] +
                           max(s[i][k] - s[i][l], k - l - s[i][k] + s[i][l]));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= t; ++j)
      for (int k = 0; k <= min(m, j); ++k)
        ans[i][j] = max(ans[i][j], ans[i-1][j-k] + f[i][m][k]);
  printf("%d\n",ans[n][t]);
}