NC20273[SCOI2009]粉刷匠

Question

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

Solution

如果我们知道对于每块木板粉刷次数对应的最优解，那这就是一个分组背包问题了。
所以我们需要预处理每块木板对应的最优解，这里要用到区间DP来求。
我们要知道每刷一次最多能刷多少块，需要用前缀和预处理1有多少块，对应的0的块数就是非1的。

1. 设表示前块木板粉刷次最多能刷多少块。
2. 

最后再用分组背包求解即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 50 + 5;

int n,m,t;
int f[N][N],dp[2505],pre[N];
char s[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++){
        memset(f,0,sizeof(f));
        cin>>s;
        for(int j=1;j<=m;j++) pre[j]=pre[j-1]+(s[j-1]=='1');//前j个里面有多少个1
        for(int j=1;j<=m;j++)
            for(int r=1;r<=m;r++)
                for(int l=0;l<r;l++)
                    f[r][j]=max(f[r][j],f[l][j-1]+max(pre[r]-pre[l],r-l-(pre[r]-pre[l])));
        for(int j=t;j>=0;j--)
            for(int k=1;k<=min(j,m);k++)
                dp[j]=max(dp[j],dp[j-k]+f[m][k]);
    }
    cout<<dp[t]<<'\n';
    return 0;
}