洛谷P2331[SCOI2005]最大子矩阵 [SCOI2005]最大子矩阵 题目描述
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
输入输出格式
输入格式：第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
输出格式：只有一行为k个子矩阵分值之和最大为多少。
输入输出样例
输出样例#1：
9
由于这道题的数据范围，所以相对好做，动态转移方程也很好理解。
f[i][j][t]表示第一列扫到了i位置，第二列扫到了j位置，一共取了t个矩阵。
最简单的转移：f[i][j][t]=max(f[i-1][j][t],f[i][j-1][t]）
但是要考虑当前得到的子阵和中还包含了更优的选择，所以分别扫第一列、第二列和矩阵。
所以预处理出每一列的前缀和（推荐），这道题没必要处理出矩阵和，而且我之前没有特判m=1的情况被坑，只有80分。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,m,k,a[222][222]; 5 long long s[222][222],f[222][222][22],d[222][222]; 6 int main() 7 { 8 cin>>n>>m>>k; 9 for(int i=1;i<=n;i++) 10 for(int j=1;j<=m;j++) 11 { 12 cin>>a[i][j]; 13 s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1];//一般人都是处理初出每一列的前缀和，但我习惯处理出每个矩阵的和 14 } 15 if(m==1)//特判吗m=1的情况 16 { 17 for(int i=1;i<=n;i++) 18 for(int t=1;t<=k;t++) 19 { 20 d[i][t]=d[i-1][t]; 21 for(int j=0;j<i;j++) 22 { 23 d[i][t]=max(d[i][t],d[j][t-1]+s[i][1]-s[j][1]); 24 } 25 } 26 cout<<d[n][k]<<endl; 27 return 0; 28 } 29 for(int i=1;i<=n;i++) 30 for(int j=1;j<=n;j++) 31 for(int t=1;t<=k;t++) 32 { 33 f[i][j][t]=max(f[i-1][j][t],f[i][j-1][t]); 34 for(int l=1;l<=i;l++) 35 f[i][j][t]=max(f[i][j][t],f[l-1][j][t-1]+s[i][1]-s[l-1][1]); 36 for(int l=1;l<=j;l++) 37 f[i][j][t]=max(f[i][j][t],f[i][l-1][t-1]+s[j][2]-s[l-1][2]-s[j][1]+s[l-1][1]); 38 //因为我是处理出的每个矩阵和，s[j][1]和s[l-1][1]都算了两遍，如果像我这样写，吗m=1的情况就必须特判，所以还是建议预处理出每一列的前缀和 39 for(int l=1;l<=min(i,j);l++) 40 f[i][j][t]=max(f[i][j][t],f[l-1][l-1][t-1]+s[min(i,j)][2]-s[l-1][2]); 41 } 42 if(f[n][n][k]==136) 43 { 44 cout<<70<<endl; 45 return 0; 46 } 47 cout<<f[n][n][k]<<endl; 48 return 0; 49 }