这道题目一开始直接写了个O(n^3*m)的dp上去，居然过了。

题目大意：
有N块木板，每块木板长度都为M，把每块木板分为M个格子，每个格子能涂红色或蓝色，每个格子只能涂一次。每次涂只能选一段连续的区域涂。现在已经给定了每块木板格子上想要的颜色，问给T次涂色机会，一共可以让多少个格子能够涂出想要的颜色。
N，M < 50,T < 2500

思路：
一开始想了个三维的dp，dp[i][j][k]表示前i块木板且当前木板前j个格子涂了k次的最大值。
那么就有：
dp[i][j][k]=dp[i][t][k-1]+max(sum[i][j]-sum[i][t],j-t-(sum[i][j]-sum[i][t])) //当前木板
dp[i][0][k]=dp[i-1][m][k-1]+max(sum[i][j],j-sum[i][j]) //上一木板的答案转移过来
由于中间要枚举一下当前木板的上一个格子位置，因此会多一个for，这样做的复杂度是O(n^3*m)，本题中大概是3 * 10^8，居然卡过去了，跑了500多ms。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,T,sum[55][55];
long long f[55][55][2555];
string s[55];
int main()
{
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='1')sum[i][j+1]=sum[i][j]+1;
            else sum[i][j+1]=sum[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=1;k<=T;k++){
                for(int t=0;t<j;t++){
                    int tmp=sum[i][j]-sum[i][t];
                    if(t==0)f[i][j][k]=f[i-1][m][k-1]+max(tmp,j-tmp);
                    else
                    f[i][j][k]=max(f[i][j][k],f[i][t][k-1]+max(tmp,j-t-tmp));
                }
            }
        }
    }
    cout<<f[n][m][T]<<endl;
}

看了下题解，用了两个dp。
其实在我一开始写的时候，突然觉得我自己的那个dp好像只能计算当前木板的情况，后来发现可以从上一块转移过来。
在题解中，则是采用计算当前木板的情况，这样子涂色的情况就最多只有m种。
可以令f[i][j][k]表示第i块木板涂了j个格子用了k次机会的最大值。
显然转移方程同上面那个几乎一样，只不过不需要从上一个木板转移过来。
然后可以把一块木板上的m种情况看成一组中的m个物品，每个物品的费用和价值分别为x和f[i][m][x]，问题变成了从N个组中每个组选1个放到容量为T的背包中让总价值最大。
也就是分组背包了。
这样子主要的复杂度为O(nmm*m)

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,T,sum[55][55];
long long f[55][55][55],dp[2555];
char s[55][55];
int main()
{
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++)scanf("%s",s[i]);
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='1')sum[i][j+1]=sum[i][j]+1;
            else sum[i][j+1]=sum[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=1;k<=min(m,j);k++){
                    for(int t=0;t<j;t++){
                        int tmp=sum[i][j]-sum[i][t];
                        f[i][j][k]=max(f[i][j][k],f[i][t][k-1]+max(tmp,j-t-tmp));
                    }

                }
            }
        }
    for(int i=1;i<=n;i++){
        for(int j=T;j>=0;j--){
            for(int k=1;k<=min(m,j);k++){
                dp[j]=max(dp[j],dp[j-k]+f[i][m][k]);
            }
        }
    }
    cout<<dp[T]<<endl;
    }

翻看题解的时候还看到大佬用4维dp[i][j][k][0/1]表示前i块木板前j个格子涂了k次并且当前这次涂0或者涂1的最大值。
有了最后一维的记录，我们就可以直接从上一个格子的状态转移过来。空间换时间血赚。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,T,sum[55][55];
long long f[55][55][2555][2];
char s[55][55];
int main()
{
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++)scanf("%s",s[i]);
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='1')sum[i][j+1]=sum[i][j]+1;
            else sum[i][j+1]=sum[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=1;k<=T;k++){
                    for(int t=0;t<=1;t++){
                        if(j==1){
                            f[i][j][k][t]=max(f[i-1][m][k-1][0],f[i-1][m][k-1][1])+(s[i][j-1]==t+'0');
                            continue;
                        }
                        f[i][j][k][t]=max(f[i][j-1][k][t],f[i][j-1][k-1][t^1])+(s[i][j-1]==t+'0');
                    }
                }
            }
        }
    cout<<max(f[n][m][T][0],f[n][m][T][1])<<endl;
    }