【每日一题】粉刷匠

题意

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

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

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

Solution：

问题是一个二维情况，即有多个木块，不好分析，先考虑一个木块的解法。
1. 表示j次涂了第i个木块前k个格子的正确格子数，j次涂至少要涂j个格子，所以 。
2.j次涂了第i个木块的正确格子数可以用j-1次涂了第i个木块的正确格子数推得，j-1次涂的格子数 ，剩余的 个格子可以选择涂蓝色或者红色。
3. 表示第i个木板前k个格子蓝色格子的数量。
4.可以推出2的状态转移方程： 。
此时考虑多块木板的情况：
1. 表示前i块木板涂了j次的正确格子数，显然可以由前i-1块木板推出前i块木板，把i块木板分成两部分 。第i块涂了k次（ ），那么前i-1块肯定涂了 次。
2.显然状态转移方程是
3.不一定是木块涂的越多越好（但涂的次数多不会比次数少差），所以要动态取ans。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
ll dp[55][2505]; 
ll f[55][2505][55];
ll sum[55][55];
int n,m,t;
char s[55];
int main() {
    read(n),read(m),read(t);
    for(int i=1;i<=n;++i) {
        scanf("%s",s+1);
        sum[i][0]=0;
        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=j;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;
}