题解 P2331 【[SCOI2005]最大子矩阵】
ttt_TTT
2018-07-02 12:02:06
~~真的坑~~
注意到m=1或者2，
当m=1时，是普通的最大连续字段和，只不过是k个：
设dp[i][j]表示前i个数中取出j个矩形的最大和
转移：
选：dp[i][j]=max{dp[l][j-1]+s[i]-s[l-1]}
不选：dp[i][j]=max(dp[i][j],dp[i-1][j])
复杂度O(n^2*K)
当m=2时，设f[i][j][k]表示第一列选到第i个数，第二列选到第j个数时，总共k个子矩形的答案
转移有4种情况
当这一位什么都不做的时候：f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k])
当仅选取第一列的某段区间时：f[i][j][k]=max(f[l][j][k-1]+sum[i][1]-sum[l-1][1]) 1<=l<i
当仅选取第二列的某段区间时：f[i][j][k]=max(f[i][l][k-1]+sum[j][2]-sum[l-1][2]) 1<=l<j
当i==j时，可以选取两列一起的f[i][j][k]=max(f[l][l][k]+sum[i][1]+sum[i][2]-sum[l-1][1]-sum[l-1][2])
最后所有情况取max
复杂度O(n^3*K)
```
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110;
const int M=11;
int n,m,K,s1[N],s2[N],dp[N][M],f[N][N][M];
int main(){
scanf("%d%d%d",&n,&m,&K);
if(m==1){
for(int i=1,x;i<=n;i++) scanf("%d",&x),s1[i]=s1[i-1]+x;
for(int k=1;k<=K;k++){
for(int i=1;i<=n;i++){
dp[i][k]=dp[i-1][k];
for(int j=0;j<i;j++) dp[i][k]=max(dp[i][k],dp[j][k-1]+s1[i]-s1[j]);
}
}
printf("%d\n",dp[n][K]);
}
else{
for(int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),s1[i]=s1[i-1]+x,s2[i]=s2[i-1]+y;
for(int k=1;k<=K;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
for(int l=0;l<i;l++) f[i][j][k]=max(f[i][j][k],f[l][j][k-1]+s1[i]-s1[l]);
for(int l=0;l<j;l++) f[i][j][k]=max(f[i][j][k],f[i][l][k-1]+s2[j]-s2[l]);
if(i==j) for(int l=0;l<i;l++) f[i][j][k]=max(f[i][j][k],f[l][l][k-1]+s1[i]-s1[l]+s2[j]-s2[l]);
}
}
}
printf("%d\n",f[n][n][K]);
}
return 0;
}
```