鏈接：

文章目錄

• • 題目描述

題目描述

這里有一個n*m的矩陣，請你選出其中k個子矩陣，使得這個k個子矩陣分值之和最大。 注意：選出的k個子矩陣 不能相互重疊。

輸入描述:

第一行為n,m,k（1 ≤ n ≤ 100,1 ≤ m ≤ 2,1 ≤ k ≤ 10），
接下來n行描述矩陣每行中的每個元素的分值(每個元素的分值的絕對值不超過32767)。

輸出描述:

只有一行為k個子矩陣分值之和最大為多少。

示例1
輸入

3 2 2 1 -3 2 3 -2 3

輸出

9

題解：
m的范圍是1~2
當m=1時，就相當于一維數組，求最大連續k段和
dp[i][j]表示前i個位置選出j段的最大價值。
轉移方程是
for(z: 1~i-1)
dp[i][j]=max(dp[i-1][j],dp[z][j-1]+sum[z~i])
sum表示z~i的元素值的和
當m=2時，
dp[i][j][l]表示第一列的前i個數，第二列的前j個數總共選了k個子矩形的答案
sum[i][1/2]表示第1列或第二列的前綴和
（其實就是 把m=1的情況進行延伸）
當i = = j時，兩列就可以拼成一個矩陣
dp[i][j][k] = max(dp[x][x][k] + sum[i][1] - sum[x-1][1] + sum[i][2] - sum[x-1][2])
僅在第一列選一個區間：
dp[i][j][k]=max(dp[x][j][k-1]+sum[i][1]-sum[x-1][1])
僅在第二列選一個區間：
dp[i][j][k]=max(dp[i][x][k-1]+sum[j][2]-sum[x-1][2])
什么都不選:
dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])
代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 105; int a[N][N]; int dp[N][N][20]; int sum[N][3]; int main() {int n,m,K;cin>>n>>m>>K;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];sum[i][j]=sum[i-1][j]+a[i][j];}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=K;k++){dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]);for(int x=0;x<i;x++)dp[i][j][k]=max(dp[i][j][k],dp[x][j][k-1]+sum[i][1]-sum[x][1]);for(int x=0;x<j;x++)dp[i][j][k]=max(dp[i][j][k],dp[i][x][k-1]+sum[j][2]-sum[x][2]);if(i==j) {for(int x=0;x<i;x++)dp[i][j][k]=max(dp[i][j][k],dp[x][x][k-1]+sum[i][1]+sum[j][2]-sum[x][1]-sum[x][2]);}}cout<<dp[n][n][K];return 0; }

總結

以上是生活随笔為你收集整理的牛客网 【每日一题】6月8日 [SCOI2005]最大子矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。