https://ac.nowcoder.com/acm/problem/20242
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。
第一行为n,m,k（1 ≤ n ≤ 100,1 ≤ m ≤ 2,1 ≤ k ≤ 10），
接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
只有一行为k个子矩阵分值之和最大为多少。
3 2 2 1 -3 2 3 -2 3
9
题解：
因为m为1或者2 分类讨论
先预处理每列的前缀和，这样两个相减即为矩阵值
m==1时 dp[i][k] 表示到第i行选j个子矩阵的最大值
每次到下一行有两种方案
不选 dp[i][k]=dp[i-1][k]
选 for（j=0;j<i;j++） dp[i][k]=max（dp[i][k], dp[j][k-1] + a[i]-a[j]）
时间复杂度 O（n^2*k）
下面讨论m==2 f[i][j][k] 表示 第一列到i行 第二列到j行 选k个子矩阵的最大值
不选 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）
#include <bits/stdc++.h> using namespace std; const int maxn=107; int a[maxn],b[maxn],dp[maxn][maxn],f[maxn][maxn][maxn]; int main(){ int n,m,x,y,p; scanf("%d%d%d",&n,&m,&p); if(m==1){ for(int i=1;i<=n;i++){ scanf("%d",&x); a[i]=a[i-1]+x; } for(int k=1;k<=p;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]+a[i]-a[j] ); } } } printf("%d\n",dp[n][p]); }else{ for(int i=1;i<=n;i++){ scanf("%d%d",&x,&y); a[i]=a[i-1]+x; b[i]=b[i-1]+y; } for(int k=1;k<=p;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] +a[i]-a[l] ); } for(int l=0;l<j;l++){ f[i][j][k]=max( f[i][j][k],f[i][l][k-1]+b[j]-b[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]+a[i]-a[l]+b[i]-b[l] ); } } } } printf("%d\n",f[n][n][p]); } return 0; } /* 3 2 2 1 9 -2 -1 3 6 */
每日一题 NC20242 [SCOI2005]最大子矩阵（动态规划 dp）
原文：https://www.cnblogs.com/lyj1/p/13398265.html
