1084: [SCOI2005]最大子矩陣

Time Limit: 10 Sec Memory Limit: 162 MB

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

Sample Output

9

題解

這題很明顯就是DP，雖然DFS也能做，但是這里主要講DP的解法。
我們讀題后會發現m只有1和2的情況，那么，分類討論。
1.m=1
矩陣就退化成了一條線。
我們設f[k][i]表示從1~i中挑選k個連續字段的最優解，那么很容易想到在前面枚舉一個j，從j+1~i為一個新的字段。
轉移方程：

f[k][i]=max(f[k][i],f[k?1][j]+sum[i]?sum[j])
sum表示前綴和。
2.m=2
我們有了m=1的想法，那么m=2就好想了。
那么就再加上一維，f[k][i][j]表示第一列挑選到i，第二列挑選到j，共有k個矩陣的最優解。
在前面枚舉個p。
轉移方程：
f[k][i][j]=max(f[k][i][j],f[k?1][p][j]+sum[i][1]?sum[p][1]);
f[k][i][j]=max(f[k][i][j],f[k?1][i][p]+sum[j][2]?sum[p][2]);
還有一種情況，就是當我們選的矩陣的寬等于2時，也就是i==j時
轉移方程：
f[k][i][j]=max(f[k][i][j],f[k?1][p][p]+mp[i][1]?mp[p][1]+mp[j][2]?mp[p][2]);

下面貼上代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,K,ans,mp[105][5],d[15][105],f[15][105][105]; int main(){scanf("%d%d%d",&n,&m,&K);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]),mp[i][j]+=mp[i-1][j];if(m==1){for(int k=1;k<=K;k++)for(int i=1;i<=n;i++){d[k][i]=d[k][i-1];for(int j=0;j<i;j++) d[k][i]=max(d[k][i],d[k-1][j]+mp[i][1]-mp[j][1]);}ans=d[K][n];}else{for(int k=1;k<=K;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){f[k][i][j]=max(f[k][i-1][j],f[k][i][j-1]);for(int p=0;p<i;p++) f[k][i][j]=max(f[k][i][j],f[k-1][p][j]+mp[i][1]-mp[p][1]);for(int p=0;p<j;p++) f[k][i][j]=max(f[k][i][j],f[k-1][i][p]+mp[j][2]-mp[p][2]);if(i==j)for(int p=0;p<j;p++) f[k][i][j]=max(f[k][i][j],f[k-1][p][p]+mp[i][1]-mp[p][1]+mp[j][2]-mp[p][2]);}ans=f[K][n][n];}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/XSamsara/p/9059460.html

總結

以上是生活随笔為你收集整理的BZOJ 1084: [SCOI2005]最大子矩阵【DP】的全部內容，希望文章能夠幫你解決所遇到的問題。

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