一開始看錯資料範圍,搞了一個 O(Tn2m2) 的,然後就GG了。
這種做法的思路是,枚舉目前狀态,可以繼續塗此層剩餘,也可以塗他層,一分類讨論即可。
後來發現這種做法肯定有大量重複,而且每行之間獨立,不必将每行的狀态混在一起,于是每行dp搞用cost最多的得分,然後行與行之間分組dp就好了。
TLE:
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxt=;
int n,m,t;
char s[maxn][maxn];
int sum[maxn][maxn];
int dp[maxt][maxn][maxn];
inline int getans(int x,int l,int r)
{
return max(sum[x][r]-sum[x][l-],r-l+-(sum[x][r]-sum[x][l-]));
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=;i<=n;i++)
scanf("%s",s[i]+);
//初始化
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
sum[i][j]=sum[i][j-]+(s[i][j]=='0');
for(int i=;i<=n;i++)
for(int k=;k<=m;k++)dp[][i][k]=getans(i,,k);
for(int i=;i<=t;i++)
{
for(int j=;j<=n;j++)//層數
{
for(int k=;k<=m;k++)//個數
{
//本層狀态
for(int l=k+;l<=m;l++)
dp[i][j][l]=max(dp[i][j][l],dp[i-][j][k]+getans(j,k+,l));
//别層狀态
for(int l=j+;l<=n;l++)
for(int p=;p<=m;p++)
dp[i][l][p]=max(dp[i][l][p],dp[i-][j][k]+getans(l,,p));
}
}
}
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
ans=max(ans,dp[t][i][j]);
printf("%d",ans);
}
AC:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxt=;
int n,m,t;
char s[maxn][maxn];
int sum[maxn][maxn];
int dp[maxn][maxt],f[maxn][maxn][maxn];
inline int getans(int x,int l,int r)
{
return max(sum[x][r]-sum[x][l-],r-l+-(sum[x][r]-sum[x][l-]));
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=;i<=n;i++)
scanf("%s",s[i]+);
//初始化
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
sum[i][j]=sum[i][j-]+(s[i][j]=='0');
//每層獨立dp
for(int i=;i<=n;i++)//層數
{
for(int l=;l<=m;l++)
f[i][][l]=getans(i,,l);
for(int j=;j<=m;j++)//次數
for(int k=j-;k<=m;k++)//上次結尾
for(int l=k+;l<=m;l++)//本次結尾
f[i][j][l]=max(f[i][j][l],f[i][j-][k]+getans(i,k+,l));
}
/*for(int i=1;i<=m;i++)
for(int j=i;j<=m;j++)
printf("%d%c",f[1][i][j],j==m?'\n':' '); */
//分組背包dp
for(int i=;i<=n;i++)//層數
for(int j=;j<=t;j++)//上次剩餘
for(int k=;k<=min(m,j);k++)//本次使用
dp[i][j-k]=max(dp[i][j-k],dp[i-][j]+f[i][k][m]);
printf("%d",dp[n][]);
return ;
}