「BZOJ1084」[SCOI2005] 最大子矩阵
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
题解
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> using namespace std; int dp[101][11],f[101][101][11]; int n,m,K; int sum[101]; int s1[101],s2[101]; int main() { int i,j,k,l; int s,ss; scanf("%d%d%d",&n,&m,&K); if(m==1) { for(i=1;i<=n;i++) {scanf("%d",&k);sum[i]=sum[i-1]+k;} for(i=1;i<=n;i++) for(k=1;k<=K;k++) { dp[i][k]=dp[i-1][k]; for(j=0;j<i;j++) dp[i][k]=max(dp[i][k],dp[j][k-1]+sum[i]-sum[j]); } cout<<dp[n][K]<<endl; } else { for(i=1;i<=n;i++) {scanf("%d%d",&s,&ss);s1[i]=s1[i-1]+s;s2[i]=s2[i-1]+ss;} for(k=1;k<=K;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]); for(l=0;l<i;l++) f[i][j][k]=max(f[i][j][k],f[l][j][k-1]+s1[i]-s1[l]); for(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(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]); } cout<<f[n][n][K]<<endl; } // system("pause"); return 0; } |
计数器 9786238
OI 课件=>
OI 课件=>
黄学长……感觉不对啊……F数组和DP数组在K!=0的时候应该是-INF…这个程序是求最多选K个子矩阵的吧……
应该是必须选取k个，不是最多选取k个