首页 > 其他 > 详细

51Nod - 1051 最大子矩阵和

时间:2017-05-09 21:18:21      阅读:255      评论:0      收藏:0      [点我收藏+]

51Nod - 1051 最大子矩阵和

一个M*N的矩阵,找到此矩阵的一个子矩阵,并且这个子矩阵的元素的和是最大的,输出这个最大的值。
 
例如:3*3的矩阵:
 
-1 3 -1
2 -1 3
-3 1 2
 
和最大的子矩阵是:
 
3 -1
-1 3
1 2
Input
第1行:M和N,中间用空格隔开(2 <= M,N <= 500)。
第2 - N + 1行:矩阵中的元素,每行M个数,中间用空格隔开。(-10^9 <= M[i] <= 10^9)
Output
输出和的最大值。如果所有数都是负数,就输出0。
Input示例
3 3
-1 3 -1
2 -1 3
-3 1 2
Output示例
7

 

 

题解: 

    简单的暴力找最大和子矩阵块。

 

 

 

#include <cstdio> 
const int MAXN = 505; 

int n, m; 
long long num[MAXN][MAXN], sum[MAXN][MAXN]; 

int main(){
	long long ans, tmp; 
	while(scanf("%d %d", &m, &n) != EOF){ 
		for(int i=1; i<=n; ++i){
			sum[i][0] = 0; 
			for(int j=1; j<=m; ++j){
				scanf("%lld", &num[i][j]); 
				sum[i][j] = sum[i][j-1] + num[i][j]; 
			}
		}
		ans = 0; 
		for(int i=0; i<=m; ++i){
			for(int j=i; j<=m; ++j){
				tmp = 0; 
				for(int k=1; k<=n; ++k){ 
					tmp += (sum[k][j] - sum[k][i]); 
					if(tmp > ans){
						ans = tmp; 
					}else if(tmp < 0){
						tmp = 0; 
					}
				}
			}
		}
		printf("%lld\n", ans );
	}
	return 0; 
}

  

 

51Nod - 1051 最大子矩阵和

原文:http://www.cnblogs.com/zhang-yd/p/6832432.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!