最大加权矩阵（洛谷）

题目

原题

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ
认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 $n\times n$
矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大矩阵的每个元素属于 $[-127,127]$ ,例如

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

在左下角：

9  2
-4  1
-1  8
1
2
3

和为 $15$。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY
小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行：$n$，接下来是 $n$ 行 $n$ 列的矩阵。

输出格式

最大矩形（子矩阵）的和。

样例 #1

样例输入 #1

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

样例输出 #1

15

提示

$1\le n\le 120$

思路

这题没想出来，后面看了下洛谷里的一些题解才懂怎么写。因此这里的思路时参考别人的代码和自己的理解。
这里和之前写过一道题目很相似。区别是前者是一维数组。二维数组由于维度变高没一维数组好写。不过二维数组可以压缩为一维数组（以前不知道还可以这样操作) 这里如果将二维数组压缩为一维数组就可以很方便求解了。二维数组压缩方法具体是：
对于一个二维数组

1 2 3
2 3 4
3 2 1
3 4 5

这里可以将这个二维数组压缩为10个一维数组。类似前后缀顺序。
压缩的一维数组分别是

将第一行和第二行每列元素相加，得到一个一维数组为：
3 5 7
将第一二三行压缩成一个数组为：
6 7 8
将一二三四行压缩为：
9 11 13
将二三行压缩为：
5 5 5
将二三四压缩为：
8 9 10
将三四压缩为;
6 6 6
最后将数组每一行作为一个一维数组
第一行：
1 2 3
第二行：
2 3 4
第三行…………

这样就完成了每个数组压缩。最后每个一维数组用求最大字段和方法得到这几个一维数组的最大字段和。最大的最大字段和就是答案。
总的来说。这里的思路就是降低维度。在进行dp前将另一个维度处理。这里是将列提前处理了，再进行dp，具体是哪几列压缩后得到的最大字段和才是最大的，我们并不清楚。因此我们遍历这10种压缩方式。同理也可以对行预处理思路是类似的就是将矩阵压缩为10个一列的数组，再对列求最大字段和。

同时还有另一个思路和我上一篇博客差不多。区别也是维度不同。方法是先将每个点的左上区域和计算出。再用一个矩阵区间和减去另几个区间和就可以得到中间区域的区域和。如此遍历，找到最大的区间和。不过这种方法时间复杂度极高。一旦矩阵大些，时间就会爆掉。因此不建议用这个方法在二维数组里。

代码

#include<iostream>
#include<cstring>
using namespace std;
int d[201][201];
int dp[201];
int lie[201];
int n;
long long int maxs=-99999999;
long long int max(long long a,int b){
	return a>b?a:b;
}
void dps(){                       		//求压缩的一维数组的最大字段和
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		dp[i]=max(lie[i],dp[i-1]+lie[i]);
		maxs=max(maxs,dp[i]);			//更新最大值
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>d[i][j];				//输入
		}
	}
	for(int i=1;i<=n;i++){
		memset(lie,0,sizeof(lie)) ;
		for(int j=i;j<=n;j++){
			for(int k=1;k<=n;k++){
				lie[k]+=d[j][k];    	//这里是遍历每种压缩方式
			}
			dps();						//将该压缩方式得到的一维数组进行求最大字段和
		}
	}
	cout<<maxs;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36