A1282 最大子矩阵

和A1224一模一样

题意

给你一个矩阵，求里面元素和最大的子矩阵，输出这个和。

题解

引理

先求最大连续子序列~ 对于一个数组b，求最大连续子序列和。 状态转移方程为dp[i]=max(b[i],b[i]+dp[i-1])。 dp[i]表示对于位置i，包含它的子序列最大值。 实际上，对于位置i，最大连续子序列和是b[i]（不包含前面最大子序列）和b[i]+dp[i-1]（包含前面最大）的最大值。最后求dp数组里最大的数，即为答案。

样例分析

用a数组存矩阵

输入：

4
0 -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

输出：15

首先，分别求每行的最大连续子序列：

4
0 -2 -7  0//最大为0
9  2 -6  2//最大为11
-4  1 -4  1//最大为1
-1  8  0 -2//最大为8
最大为11

然后，求两行在一起的最大子序列，将上下两行加起来，用b数组来存：

4
0 -2 -7  0
9  2 -6  2//9 0 -13 2，最大为9
-4  1 -4  1//5 3 -10 3，最大为8
-1  8  0 -2//-5 9 -4 -1，最大为9
最大为9

继续求三行，四行在一起的最大子序列。 用ans求出最大的值，就是答案了。

呆马

#include<bits/stdc++.h>
using namespace std;
int a[105][105],b[105][105],dp[105],ans,n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		cin>>a[i][j];//a数组存储矩阵
	}
	for(int i=1;i<=n;i++){
		memset(b,0,sizeof(b));//初始化b数组
		for(int j=i;j<=n;j++){
			for(int k=1;k<=n;k++)
			b[j][k]=a[j][k]+b[j-1][k];//求出从1到n行加在一起的数组
			memset(dp,0,sizeof(dp));//初始化dp数组
			for(int k=1;k<=n;k++){
				dp[k]=max(b[j][k],b[j][k]+dp[k-1]);//由引理得(没看懂再回去看一遍）
				ans=max(ans,dp[k]);//求最大值
			}
		}
	}
	cout<<ans<<endl;//输出答案
	return 0;
}

点赞！！！！！！！