其实那,我是被标题吸引来的

你康康,最大子矩阵!多么人畜无害的名字啊~~~

然后发生了什么吗大家都应该猜到啦!然后一读题,让你求出k个子矩阵的最大值!

但是呢?发现这是一个n*m的矩阵废话!然后.. m = 1 或者 2 !! 你 说 话 怎 么 带 空 格 啊 啊 啊

第一种 m = 1 , 感觉很水 啊!!

你看看,不就变成了一个一维的辣!

设f[i][j] 表示 从前 i 个 数中取出j个子矩阵的最大答案

那么,就扫一遍,如果不选的话,f[i][j] = max(f[i-1][j])

选的话就是f[i][j] = max(f[0 to i][j-1] + 所选范围的和)

阶段性code

 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]) ; } } }

下面就是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])

至于代码,就是,,

 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]); } } } } }

总代码

#include <bits/stdc++.h> #define maxn 120 #define maxm 20 using namespace std ; int n , m , K , s1[maxn] , dp[maxn][maxm] , f[maxn][maxn][maxm] , s2[maxn] ; int main () { scanf("%d%d%d",&n,&m,&K) ; if(m == 1){ int x ; for(int i = 1 ; i <= n ; i ++) { cin >> 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 ; i <= n ; i ++) { int x , y ; cin >> 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]); } } } } } cout << f[n][n][K] << endl ; } return 0 ; }