频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 1050 二维动态规划转变成枚举加一维的动态规划!
2015-04-21 10:11:42         来源:点羽染墨  
收藏   我要投稿
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 

using namespace std;

int n;
int a[105][105];
int dp[105][105];
int sum[105][105];


int main(){
	while(scanf("%d",&n)!=EOF){
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				scanf("%d",&a[i][j]);
			}
		}
		memset(dp,0,sizeof(dp));
	
		for(int j = 1;j <= n;j++){ // j列的前缀和 
			for(int i = 1;i <= n;i++){
				sum[j][i] = sum[j][i-1] + a[i][j];
			}
		}
		for(int i = 1;i <= n;i++){
			for(int j = i;j <= n;j++){
				int right = 0;
				for(int k = 1;k <= n;k++){
					 if(right >= 0){
					 	right += sum[k][j] - sum[k][i-1]; 
					 }
					 else{
					 	right = sum[k][j] - sum[k][i-1]; 
					 }
					 
					 dp[i][j] = max(dp[i][j],right);
					 
				} 
			}
		}		
		int ans = -INT_MAX;
		for(int i = 1;i <= n;i++){
			for(int j = i;j <= n;j++){
				if(dp[i][j] > ans){
					ans = dp[i][j];
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

点击复制链接 与好友分享!回本站首页
相关TAG标签 一维 二维 动态
上一篇:pku3090 Visible Lattice Points:人生第一个欧拉函数
下一篇:hdu 3572 Task Schedule 最大流 Dinic算法,,卡时间。。建图非常有讲究
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站