题目

题目描述

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

输入描述

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

输出描述

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

示例

输入：
3 6 3
111111
000000
001100

输出：
16

思路

参照了大佬的题解，大佬博客
全部的数据，满足1<=N,M<=50;0<=T<=2500.
题意一次只能粉刷一块木板，因此我们将题目分解成两次dp，单块木板进行dp，木板之间进行，也就是二维dp。首先我们通过一个三维数组f[i][j][k]表示第i块木板粉刷了j次，涂了前面k个格子的正确格子数。*对应一个木板，只存在红蓝两种颜色，在输入数据时，通过处理前缀和，可以得知某个位置前某种颜色格子数。*
假设前缀和记录蓝色,sum数组记录前缀和，则有sum[k] - sum[l]表示[l,k]的蓝色格子；
k - l - (sum[k] - sum[l])表示[l,k]的红色格子数。
那么对于每块木板得到三维状态转移方程

f[i][j][k]=max(f[i][j][k],f[i][j-1][l]+max(sum[k]-sum[l],k-l-(sum[k]-sum[l])))

截取l这个决策点位置涂到状态k，取涂蓝色或者红色的最大值即可。

那么处理得到了上面这个三维的f数组，对于二维的木板填涂方法来说，也就是木板之间的dp。

dp[i][j]=dp[i-1][j-k]+f[i][k][m]dp[i][j]=dp[i−1][j−k]+f[i][k][m]

前面i - 1块木板涂 j - k次，剩余的k交给第i块木板涂满m个格子。

code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 55;
const int M = 2505;
ll dp[N][M];    // dp[i][j]   前i个木板粉刷j次的正确格子数
ll f[N][M][N]; // f[i][j][k] 第i个木板粉刷j次涂了前面k个格子的正确格子数
ll sum[N][N]; // sum[i][j] 第i个木板第j个木板前蓝色格子的数目
char s[N];

int main() {
    int n = read(), m = read(), t = read();
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        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]);
        }
    printf("%lld\n", ans);
    return 0;
}

/*
3 6 3
111111
000000
001100

16
*/

【每日一题】5月6日粉刷匠

题目

题目描述

输入描述

输出描述

示例

思路

code