P1719 最大加权矩形

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

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

输出

15
1

动态规划
这个题可以看做是“最大字段和”在高维的情况。
具体思路是：枚举top行和bottom行，求这几行的每一列的列和，得到一个一维数组，求这个数组的最大子段和。求列和时，因为bottom是递增的，每次bottom+1之后，对应列的列和+arr[bottom]

#include
#include
#include
using namespace std;
int maxsum(int arr[],int n){
	int pre=arr[0];
	int res=pre;
	for(int i=1;i<n;i++){
		pre=max(pre+arr[i],arr[i]);
		res=max(res,pre);
	}
	return res;
}
int main(){
	int n;
	cin>>n;
	int arr[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>arr[i][j];
		}
	}
	int res=INT_MIN;
	for(int top=0;top<n;top++){
		int sum[n];
		memset(sum,0,sizeof(sum));
		for(int bottom=top;bottom<n;bottom++){
			for(int i=0;i<n;i++){
				sum[i]+=arr[bottom][i];
			}
			int curmax=maxsum(sum,n);
			res=max(res,curmax);
		}
	}
	cout<<res;
	return 0;
}
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
37