每日一题：粉刷匠（背包dp）

题意

n 条木板，每条木板都被分成 m 段且每一段都有要涂的颜色，有 t 次机会涂色，每次可以选择一条木板的连续一段涂成同一种颜色，问最多可以涂对多少段。

solution

考虑四维dp的做法。$dp[i][j][k][0/1]$ 代表到第 $i$ 条第 $j$ 段时涂 $k$ 次，当前段涂红或蓝$(0/1)$的最大正确数，可以得到转移方程：

当 $j=1$ (属于当前木板第一段) 时，由上一个木板转移过来：

$dp[i][j][k][0] = max(dp[i-1][m][k-1][0],dp[i-1][m][k-1][1]) + (s[i][j] == ‘0’)$

$dp[i][j][k][1] = max(dp[i-1][m][k-1][0],dp[i-1][m][k-1][1]) + (s[i][j] == ‘1’)$

否则，由当前木板的上一段转移过来：

$dp[i][j][k][0] = max(dp[i][j-1][k][0],dp[i][j-1][k-1][1]) + (s[i][j] == ‘0’)$

$dp[i][j][k][1] = max(dp[i][j-1][k-1][0],dp[i][j-1][k][1]) + (s[i][j] == ‘1’)$

最后结果显然为 $max(dp[n][m][t][0], dp[n][m][t][1])$ 。

时间复杂度 $O(nmt)$，空间上可以使用滚动数组压维，空间复杂度为 $O(4mt)$。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
char s[N][N];
int n, m, t, dp[2][N][N * N][2];

int main() {
  scanf("%d%d%d", &n, &m, &t);
  for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      for (int k = 1; k <= t; k++)
        for (int l = 0; l <= 1; l++) {
          if (j == 1)
            dp[i & 1][j][k][l] = max(dp[(i - 1) & 1][m][k - 1][0], dp[(i - 1) & 1][m][k - 1][1]) + (s[i][j] == l + '0');
          else
            dp[i & 1][j][k][l] = max(dp[i & 1][j - 1][k][l], dp[i & 1][j - 1][k - 1][l ^ 1]) + (s[i][j] == l + '0');
        }
  printf("%d\n", max(dp[n & 1][m][t][0], dp[n & 1][m][t][1]));
  return 0;
}