[文章目录]
Description
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。1<=N,M<=25 ，0<=T<=2500
对于每一行单独DP刷i次的正确粉刷数。dp[i][j]表示前i个刷了j次的最多的正确粉刷数。
每一行复杂度O(m^3)总复杂度O(n*m^3)
之后不同的木板间跑分组背包即可。
时间复杂度O(n*m*T)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,t,dp[60][60],mp[60][60],s1[60],s0[60],f[60][2600];
char s[100];
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int c=1;c<=n;++c)
{
scanf("%s",s+1);
for(int j=1;j<=m;++j)
{
s1[j]=s1[j-1]+(s[j]=='1');
s0[j]=s0[j-1]+(s[j]=='0');
}
memset(dp,0,sizeof dp);
for(int i=1;i<=m;++i)
for(int j=1;j<=i;++j)
for(int k=0;k<i;++k)
dp[i][j]=max(dp[i][j],dp[k][j-1]+max(s1[i]-s1[k],s0[i]-s0[k]));
for(int j=0;j<=m;++j)
{
int mx=-inf;
for(int i=0;i<=m;++i) mx=max(mx,dp[i][j]);
mp[c][j]=mx;
}
}
for(int i=1;i<=n;++i)
{
for(int j=t;j>=0;--j)
{
for(int k=0;k<=j&&k<=m;++k)
f[i][j]=max(f[i][j],f[i-1][j-k]+mp[i][k]);
}
}
printf("%d",f[n][t]);
return 0;
}