洛谷P4158 [SCOI2009]粉刷匠 题解

题目链接：P4158 [SCOI2009]粉刷匠

题意：windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。

windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。

如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

比较简单的dp

设 $f[i][j]$ 为前 $i$ 块木板粉刷 $j$ 次的情况下能正确粉刷的最大格子数

设 $g[i][j][k]$ 为第 $i$ 条木板粉刷 $j$ 次且只涂了前 $k$ 个格子的情况下能正确粉刷的最大格子数

设 $S[i][j]$ 为第 $i$ 条木板前 $j$ 个格子的蓝色格子数

不难发现

$$f[i][j]=\max(f[i][j],f[i-1][j-k]+g[i][k][m]) \\g[i][j][k]=\max(g[i][j][k],g[i][j-1][l]+\max(S[i][k]-S[i][l],k-l-(S[i][k]-S[i][l])))$$

时间复杂度 $O(n^4+n^2T)$ （ $n,m$ 同阶）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(55)
#define T (int)(3e3+15)

char s[N];
int n,m,t;
int f[N][T],sum[N][T],g[N][T][N];
void Max(int &a,int b)
{
    if(b>a)a=b;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> t;
    for(int i=1; i<=n; i++)
    {
        cin >> s;
        for(int j=1; j<=m; j++)
            sum[i][j]=sum[i][j-1]+(s[j-1]=='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++)
        Max(g[i][j][k],g[i][j-1][l]+max(sum[i][k]-sum[i][l],k-l-sum[i][k]+sum[i][l]));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=t; j++)
            for(int k=0; k<=min(j,m); k++)
                Max(f[i][j],f[i-1][j-k]+g[i][k][m]);
    cout << *max_element(f[n]+1,f[n]+1+t) << endl;
    return 0;
}