首页 > 代码库 > BZOJ: 1084: [SCOI2005]最大子矩阵
BZOJ: 1084: [SCOI2005]最大子矩阵
NICE 的DP 题，明白了题解真是不错。
Submit: 1228 Solved: 622
[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
1 -3
2 3
-2 3
Sample Output
9
HINT
思路：M<=2;
先是M==1的情况 这个是满满的三维。DP[I][J】表示做的第几个，现在做到J个数了。转移也比较简单。
M==2时，
我们要加一维。
具体是这样：F[I][J][K] 表示做第I个 J 表示上面做到第几，K表示下面做到第几。
转移方程：具体见代码。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 123 4 int s[N]; 5 int s1[N]; 6 int s2[N]; 7 int a[N]; 8 int dp[N][N]; 9 int f[N][N][N];10 int main()11 {12 int n;13 int k;14 int m;15 scanf("%d%d%d",&n,&m,&k);16 if (m==1){17 for (int i=1;i<=n;i++) {18 scanf("%d",&a[i]);19 s[i]=s[i-1]+a[i];20 }21 for (int i=1;i<=k;i++)22 for (int j=1;j<=n;j++)23 {24 dp[i][j]=dp[i][j-1];25 for (int p=0;p<j;p++)26 dp[i][j]=max(dp[i][j],dp[i-1][p]+s[j]-s[p]);27 }28 printf("%d\n",dp[k][n]);29 }30 else31 {32 for (int i=1;i<=n;i++)33 {34 int x1,x2;35 scanf("%d%d",&x1,&x2);36 s1[i]+=s1[i-1]+x1;37 s2[i]+=s2[i-1]+x2;38 }39 40 for (int i=1;i<=k;i++)41 for (int j=1;j<=n;j++)42 for (int p=1;p<=n;p++)43 {44 f[i][j][p]=max(f[i][j-1][p],f[i][j][p-1]);45 for (int l=0;l<j;l++)46 f[i][j][p]=max(f[i][j][p],f[i-1][l][p]+s1[j]-s1[l]);47 48 for (int l=0;l<p;l++)49 f[i][j][p]=max(f[i][j][p],f[i-1][j][l]+s2[p]-s2[l]);50 51 if (j==p)52 {53 for (int l=0;l<j;l++)54 f[i][j][p]=max(f[i][j][p],f[i-1][l][l]+s2[p]-s2[l]+s1[p]-s1[l]);55 }56 }57 58 printf("%d\n",f[k][n][n]);59 }60 return 0;61 }
BZOJ: 1084: [SCOI2005]最大子矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。