[题解] [洛谷P4158] 粉刷匠

题目描述

有 \(n\) 个木板，每个木板有 \(m\) 个格子，所有格子最开始视为没有颜色。

有 \(0/1\) 两种颜色，每次可以粉刷其中一块木板上一段连续的格子，总共可以粉刷 \(t\) 次。

给出一组目标颜色，问最多可以将多少个格子粉刷成目标颜色。

输入格式

第一行包含三个整数， \(n,m,t(1 \leq n,m \leq 10, 0 \leq t \leq 100)\)

接下来 \(n\) 行，每行一个长度为 \(m\) 的 \(0/1\) 字符串，表示木板颜色

输出格式

包含一个整数，表示能正确粉刷的最多格子数。

题解

为了更直观的求解，本题可以拆分为两个子问题：求第 \(i\) 个木板粉刷 \(j\) 次能够粉刷的最多格子数 \(b_{i,j}\) ，再利用得到的答案求解用前 \(i\) 个木板粉刷 \(j\) 次能够粉刷的最多格子数。

先看第一个子问题，设计状态 \(f_{i,j,k,(0/1)}\) 表示第 \(i\) 个木板的前 \(j\) 个方块粉刷 \(k\) 次，且当前方块粉刷成 \(0/1\) 状态的最大格子数。因为对于每一个格子来说，我们是否需要多消耗一次粉刷次数只取决于粉刷它的上一个格子的时候是否用了和它一样的颜色。假设当前格子颜色是 \(c\) ，可以得到状态转移方程： \(f_{i,j,k,c} = max(f_{i,j-1,k,c} + 1, f_{i,j-1,k-1,!c} + 1)\) 与 \(f_{i,j,k,!c} = max(f_{i,j-1,k,!c}, f_{i,j-1,k-1,c})\)即在是否选择新粉刷一次中选一个更优状态。

第二个子问题就比较简单了，设计状态 \(dp_{i,j} = max(f_{i,m,k} + dp_{i-1,j-k})\) 其中 \(dp_{i,j}\) 表示前 \(i\) 个木板粉刷 \(j\) 次的最大格子数， \(k\) 是在第 \(i\) 个木板粉刷的次数。枚举 \(k\) 转移即可。

AC 代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;

const int MAXN = 53;
const int MAXT = 2503;

int n, m, t;
int a[MAXN][MAXN];

int f[MAXN][MAXN][MAXT][2]; // 表示第i块木板的前j个格子粉刷k次得到的最高分数，并且当前正在粉刷0/1
int dp[MAXN][MAXT];

signed main() {
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            a[i][j + 1] = s[j] - '0';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= t; k++) {
            for (int j = 1; j <= m; j++) {
                const int c = a[i][j]; // 当前格子的颜色
                // 刷当前的颜色
                f[i][j][k][c] = max(f[i][j - 1][k][c] + 1, f[i][j - 1][k - 1][!c] + 1);
                // 不刷当前的颜色
                f[i][j][k][!c] = max(f[i][j - 1][k][!c], f[i][j - 1][k - 1][c]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) { // 前i个木板
        for (int j = 1; j <= t; j++) { // 一共粉刷j次
            for (int k = 1; k <= j; k++) { // 在当前木板粉刷k次
                // 更新答案
                dp[i][j] = max(dp[i][j], max(f[i][m][k][0], f[i][m][k][1]) + dp[i - 1][j - k]);
                ans = max(ans, dp[i][j]);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}