Poj 1050 c++:To the Max

2017-01-05 20:04:44来源:CSDN作者:u010203544人点击

第七城市

思路:

将二维的压缩到一维进行考虑,压缩的过程是暴力的,dp[i][j] 表示的是以1,1到i,i这矩形内的数字和,在初始输入数组的时候就计算dp,后面遍历所有行的组合
#include <stdio.h>#include <iostream>using namespace std;int n;int dp[501][501];int a[501][501];int main(){	cin>>n;	int i,j;	for(i=1;i<=n;i++){		for(j=1;j<=n;j++){			scanf("%d",&a[i][j]);			dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i][j];		}	}	int k,sum=0,sum1;	int maxv=-9999;	for(i=1;i<=n;i++){		for(j=i;j<=n;j++){			sum=0;			for(k=1;k<=n;k++){				sum1=-dp[i-1][k]-dp[j][k-1]+dp[i-1][k-1]+dp[j][k];				if(sum>0){					sum+=sum1;				}				else sum=sum1;				if(sum>maxv) maxv=sum;			}		}	}	cout<<maxv<<endl;			return 0;}


第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台