洛谷P4158 [SCOI2009]粉刷匠 题解

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

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

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

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

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

比较简单的dp

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

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

设 S [ i ] [ j ] S[i][j] S[i][j] 为第 i i i 条木板前 j j 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 ] ) ) ) 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]))) 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 2 T ) O(n^4+n^2T) O(n4+n2T) （ n , m n,m n,m 同阶）

代码：

#include 
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 
转载请说明出处