首页 > 代码库 > uva10827-Maximum sum on a torus(矩阵最大和的变形)
uva10827-Maximum sum on a torus(矩阵最大和的变形)
题目;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(矩阵最大和的变形)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。