【原题】
1084: [SCOI2005]最大子矩阵
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1016 Solved: 518
[Submit][Status]
Description
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
Input
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
Output
只有一行为k个子矩阵分值之和最大为多少。
Sample Input
3 2 2
1 -3
2 3
-2 3
Sample Output
9
【分析】照理来说是一个很简单的DP。因为M<=2，所以明摆着分情况做。但是我开始写的DP一直萎，不知道为什么。后来去网上开了题解，发现我的想法和意义都是对的，但是转移的时候我少了一维（详见代码）只能说呵呵了。虽然我和标解看上去都对，但是我还是想不通为什么我的不可以。
【自己的想法】
#include
#include
#define N 105 #define K 15 using namespace std; int s[N],sum1[N],sum2[N],g[N][K],f[N][N][K]; int n,m,ans,L; inline int max3(int x,int y,int z){return max(max(x,y),z);} inline int max4(int x,int y,int p,int q){return max(max(x,y),max(p,q));} void solve_1() { for (int i=1;i<=n;i++) scanf("%d",&s[i]); for (int i=1;i<=n;i++) { g[i][1]=g[i-1][1]+s[i]; for (int j=2;j<=L;j++) g[i][j]=max3(g[i-1][j],g[i-1][j]+s[i],g[i-1][j-1]+s[i]); } ans=g[n][L]; } void solve_2() { for (int i=1;i<=n;i++) scanf("%d%d",&sum1[i],&sum2[i]); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { f[i][j][1]=f[i-1][j-1][1]+sum1[i]+sum2[j]; for (int k=2;k<=L;k++) { f[i][j][k]=max3(f[i-1][j][k],f[i-1][j][k]+sum1[i],f[i-1][j][k-1]+sum1[i]); f[i][j][k]=max4(f[i][j][k],f[i][j-1][k],f[i][j-1][k]+sum2[j],f[i][j-1][k-1]+sum2[j]); if (i==j) f[i][j][k]=max4(f[i][j][k],f[i-1][j-1][k],f[i-1][j-1][k]+sum1[i]+sum2[j],f[i-1][j-1][k-1]+sum1[i]+sum2[j]); } } ans=f[n][n][L]; } int main() { scanf("%d%d%d",&n,&m,&L); if (m==1) solve_1(); if (m==2) solve_2(); printf("%d",ans); return 0; }
【AC代码】
#include
#include
#define N 105 #define K 15 using namespace std; int s[N],sum1[N],sum2[N],g[N][K],f[N][N][K]; int n,m,ans,L; void solve_1() { for (int i=1;i<=n;i++) scanf("%d",&s[i]),s[i]+=s[i-1]; for (int i=1;i<=n;i++) for (int k=1;k<=L;k++) { g[i][k]=g[i-1][k]; for (int j=0;j