好贷网好贷款

UVA 10827 Maximum sum on a torus 可循环的最大连续子矩阵

发布时间:2016-12-4 7:51:41 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVA 10827 Maximum sum on a torus 可循环的最大连续子矩阵",主要涉及到UVA 10827 Maximum sum on a torus 可循环的最大连续子矩阵方面的内容,对于UVA 10827 Maximum sum on a torus 可循环的最大连续子矩阵感兴趣的同学可以参考一下。

这题其实是uva 108的拓展,就是给出的矩阵中子矩阵的定义变成可循环的,比如下面这样是一个3*3的子矩阵: 1 -1 0 0 -4 2 3 -2 -3 2 4 1 -1 5 0 3 -2 1 -3 2 -3 2 4 1 -4 只要把矩阵拓展成四倍大,然后处理一下子矩阵不能大于N*N,然后按普通的最大连续矩阵做就可以了。 代码: /* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: uva827.cpp * Lauguage: C/C++ * Create Date: 2013-09-05 16:36:28 * Descripton: UVA 10827 Maximum sum on a torus, dp */ #include <cstdio> #include <algorithm> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) #define repf(i, a, b) for (int i = (a); i <= (b); i++) const int MAXN = 160; int m[MAXN][MAXN], s[MAXN][MAXN], a[MAXN], n; void maxSeq(int* a, int len, int &res) { res = a[0]; int sum = 0; for (int i = 0; i < len; i++) { if (sum <= 0) sum = a[i]; else sum += a[i]; if (res < sum) res = sum; } } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); repf(i, 1, n) repf(j, 1, n) { scanf("%d", &m[i][j]); m[i + n][j] = m[i][j + n] = m[i + n][j + n] = m[i][j]; } repf(i, 1, 2 * n - 1) repf(j, 1, 2 * n - 1) s[i][j] = s[i - 1][j] + m[i][j]; int ans = -0xfffffff, res; repf(i, 0, n - 1) repf(j, i + 1, i + n) { rep(l, n) { repf(k, 1, n) a[k] = s[j][k + l] - s[i][k + l]; maxSeq(a + 1, n, res); ans = max(ans, res); } } printf("%d\n", ans); } return 0; }

上一篇:拓扑排序
下一篇:bat 文件夹移动

相关文章

相关评论