Maximum sum on a torus
Input: Standard Input
Output: Standard Output
A grid that wraps both horizontally and vertically is called a torus. Given a torus where each cell contains an integer, determine the sub-rectangle with the largest sum. The sum of a sub-rectangle is the sum of all the elements in that rectangle. The grid
below shows a torus where the maximum sub-rectangle has been shaded.
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 |
Input
The first line in the input contains the number of test cases (at most 18). Each case starts with an integer N (1≤N≤75) specifying the size of the torus (always square). Then follows N lines describing the torus, each line containing N integers between-100
and 100, inclusive.
Output
For each test case, output a line containing a single integer: the maximum sum of a sub-rectangle within the torus.
Sample Input
2
5
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
3
1 2 3
4 5 6
7 8 9
Output for Sample Input
1545
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1768这道题是求最大子矩阵和的加强版,原矩阵是一个上下左右都可以串通的矩阵环,通过在原矩阵的下方,右方和右下方添加相同的矩阵,然后枚举所求最大子矩阵在第一个矩阵中的左上角,再通过动态规划的方法求出长宽不大于N的最大子矩阵,各种枚举情况中的最大和即为所求解。#include <cstdio> using namespace std; #define MAX 155 int main() { int x,y,i,j,n,s,ans; int c[MAX],b[MAX],a[MAX][MAX]; scanf("%d",&s); while (--s>=0){ scanf("%d",&n); for(i=0;i<n;++i) for (j=0;j<n;++j){ scanf("%d",&a[i][j]); a[i][j+n]=a[i+n][j]=a[i+n][j+n]=a[i][j]; } ans=-200; for (x=0;x<n;++x) for(y=0;y<n;++y) for(i=0;i<n;++i) for(j=0;j<n;++j) { c[j]=a[x+i][y+j]; if(j) c[j]+=c[j-1]; if(i) b[j]+=c[j]; else b[j]=c[j]; if (b[j]>ans) ans=b[j]; } printf("%d\n",ans); } return 0; }