首页 > 其他 > 详细

uva10827-Maximum sum on a torus(矩阵最大和的变形)

时间:2014-07-17 19:36:16      阅读:389      评论:0      收藏:0      [点我收藏+]

题目;uva10827-Maximum sum on a torus(矩阵最大和的变形)


题目大意:就是uva108的变形,矩阵能够连通,就是可以从后面连到前面。这里把矩阵复制三遍,然后重新生成一个大的矩阵,就可以解决联通的问题。再枚举矩阵的起点和终点所有情况,保留最大值就可以了。

例如:1 2 3

       2 3 4

新的矩阵: 1 2 3  1 2 3

                   2 3 4  2 3 4

                   1 2 3   1 2 3

                   2 3 4   2 3 4


代码:

#include <stdio.h>
#include <string.h>

const int N = 200;
const int INF = 0x3f3f3f3f;
int mat[N][N], temx[N], temy[N];
int n;

int Max (const int x, const int y) {return x > y? x: y;}

int main () {

	int t;
	scanf ("%d", &t);
	while (t--) {

		scanf ("%d", &n);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {

				scanf ("%d", &mat[i][j]);
				mat[i][j + n] = mat[i + n][j] = mat[i + n][j + n] = mat[i][j];
			}
		
		int mm = -INF;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {

				memset (temx, 0, sizeof (temx));
				for (int x = i; x < i + n; x++) {	
					for (int y = j; y < j + n; y++) {
						
							if (y == j)
								temy[y] = mat[x][y];
							else
								temy[y] = temy[y - 1] + mat[x][y];
							temx[y] += temy[y];	
							mm = Max (mm, temy[y]);
							mm = Max (mm, temx[y]);
					}
			}
		}
	}
	printf ("%d\n", mm);
	}
	return 0;
}


uva10827-Maximum sum on a torus(矩阵最大和的变形),布布扣,bubuko.com

uva10827-Maximum sum on a torus(矩阵最大和的变形)

原文:http://blog.csdn.net/u012997373/article/details/37908047

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