题解 | #[SCOI2009]粉刷匠#

//分组背包问题，首先考虑一个木板的情况：
//对于一个木板而言：dp[i][j]，i表示当前是第i次粉刷，粉刷第j块格子的情况。
//那么得到状态转移方程为：dp[i][j] = max(dp[i-1][l]+num[l+1][j])。
//其中num[l+1][j]表示在l到j这个区间里面最大的有效格子是多少。
//然后将其扩展到多个木板即在一维加上木板。
//dp[k][i][j]。
//首选一次动态规划求出每一个木板涂i次的最好情况。
//dp[k][i][j] = max(dp[k][i-1][l]+num[l+1][j]);
//然后用每个木块的最终结果做第二次总的动态规划
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
int n, m, t;
int num[maxn][maxn][maxn];
int dp[maxn][2500+10][maxn];
int ans[maxn][2500+10];

void calc(int pos, string s)
{
    int len = s.size();
    for (int i=1;i<=len-1;i++)
    {
        for (int j=i;j<=len-1;j++)
        {
            int cnt1 = 0, cnt2 = 0;
            for (int k=i;k<=j;k++)
            {
                if (s[k]=='0') cnt1++;
                if (s[k]=='1') cnt2++;
            }
            num[pos][i][j] = max(cnt1, cnt2); 
        }
    }
}

int main(){
    cin>>n>>m>>t;
    for (int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        s = " "+s;
        calc(i, s);
    }
    //进行第一次针对于各个木板的动态规划
    for (int k=1;k<=n;k++)
    {
        for (int i=1;i<=t;i++)
        {
            for (int j=1;j<=m;j++)
            {
                for (int l=1;l<=j;l++)
                {
                    dp[k][i][j] = max(dp[k][i][j], dp[k][i-1][l-1]+num[k][l][j]);
                }
            }
        }
    }
//     for (int k=1;k<=n;k++)
//     {
//         for (int i=1;i<=t;i++)
//         {
//             cout<<dp[k][i][m]<<endl;
//         }
//     }
    //dp[k][i][m] = max(dp[k-1][i-l][m]+dp[k][l][m]);
    for (int k=1;k<=n;k++)
    {
        for (int i=1;i<=t;i++)
        {
            for (int l=1;l<=i;l++)
            {
                ans[k][i] = max(ans[k][i], ans[k-1][i-l]+dp[k][l][m]);
//                 cout<<"k="<<k<<' '<<ans[k][i][m]<<endl;
//                 cout<<dp[k-1][i-l][m]<<' '<<dp[k][l][m]<<endl;
            }
        }
    }
    cout<<ans[n][t]<<endl;
    
    return 0;
}