P1719 最大加权矩形

思路

方法：前缀和

提示：x1,y1到x2,y2的区间和=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1].

步骤：

1.计算每一个坐标的前缀和

2.计算每一个x1,y1到x2,y2的区间和：

        2.1按照以上公式计算

        2.2将结果与现有的最大结果进行比较，存储最大结果作为ans

3.输出ans（最大结果）

代码 

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,sum[125][125],ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int a;
			cin>>a;
			sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a;
		}
	}
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=n;y1++){
			for(int x2=1;x2<=n;x2++){
				for(int y2=1;y2<=n;y2++){
					if(!(x1<=x2&&y1<=y2)) continue;
					int newAns=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
					//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<newAns<<endl; 
					ans=max(ans,newAns);
				}
			}
		}
	} 
	cout<<ans;
	return 0;
}