【每日一题】 粉刷匠

动态规划。

原问题：n个木板粉刷t次的最多粉刷个数
子问题：前i个木板刷j次的最多粉刷个数
描述：记dp1[i][j]表示前i个木板刷j次的最多粉刷个数
推出dp1[i][j]=max{dp1[i-1][j-k]+第i个板粉刷k次的最多粉刷个数},k<=j

这又产生了新问题，如何求某个板粉刷某次的最多个数呢？
用第二层动态规划：
原问题：某板整体粉刷k次的最多粉刷个数
子问题：某板前j块刷k次得最多粉刷个数
描述：记dp2[j][k]表示某板前j块刷k次得最多粉刷个数
因为每次粉刷连续一段，所以考虑第j块时可以考虑从第j块前面的第l块一直刷到第j块，刷的颜色取决于这一段红蓝两色应刷的个数；预处理sum[i]数组表示该板前i块有多少应刷成蓝色，则sum[j]-sum[j-l]和l-(sum[j]-sum[j-l])分别表示红蓝两色应刷的个数；推出dp2[j][k]=max{dp[j-l][k-1]+max(sum[j]-sum[j-l],l-(sum[j]-sum[j-l]))},l<=j。

这样则推出：dp1[i][j]=max(dp1[i][j],dp1[i-1][j-k]+dp2[m][min(k,m)])。
因为每块板最多粉刷m次即可，所以对其粉刷次数取最小值。
最后输出dp1[n][t]即可。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=1e5+9;
const int maxx=1e4+9;

int n,m,t;
char ar[55][55];
int dp1[55][2555],dp2[55][55],sum[55];
//前i个板涂j次最多个数  前i格涂j次最多个数

int main()
{
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++) cin>>(ar[i]+1);
    for(int i=1;i<=n;i++)
    {
        memset(dp2,0,sizeof dp2);
        memset(sum,0,sizeof sum);
        for(int j=1;j<=m;j++)
        {
            sum[j]=sum[j-1];
            if(ar[i][j]=='1') sum[j]++;
        }
        for(int j=1;j<=m;j++)
            for(int k=1;k<=m;k++)
            {
                for(int l=0;l<=j;l++)
                    dp2[j][k]=max(dp2[j][k],dp2[j-l][k-1]+max(sum[j]-sum[j-l],l-(sum[j]-sum[j-l])));
            }
        for(int j=1;j<=t;j++)
            for(int k=0;k<=j;k++)
                dp1[i][j]=max(dp1[i][j],dp1[i-1][j-k]+dp2[m][min(k,m)]);
    }
    cout<<dp1[n][t]<<endl;
}