UVA 10827 Maximum sum on a torus 最大矩阵和

题意描述：给出一个n*n矩阵，把第一行和最后一行粘一起，把第一列和最后一列粘一起，形成一个环面，求出这个环面中最大的矩阵和。

算法分析：首先复制n*n这个矩阵，形成由4个这样小矩阵组成的大矩阵，然后在这个大矩阵里找出最大矩阵和，一看貌似和poj1050这道题有些相似，但是这道题数据大一些，O(150^4)应该会超时吧。我们可以这样想，先枚举这个最大和矩阵的左上角在大矩阵中的位置，然后枚举最大和矩阵的行数和列数，在枚举过程中处理最大和，然后更新答案即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 using namespace std;
 9 const int maxn=160;
10 
11 int n,an[maxn][maxn];
12 int r[maxn],c[maxn];
13 
14 int main()
15 {
16     int t;
17     scanf("%d",&t);
18     while (t--)
19     {
20         scanf("%d",&n);
21         for (int i=1 ;i<=n ;i++)
22         {
23             for (int j=1 ;j<=n ;j++)
24             {
25                 scanf("%d",&an[i][j]);
26                 an[i+n][j]=an[i][j+n]=an[i+n][j+n]=an[i][j];
27                 //构成了四个小矩阵形成的大矩阵
28             }
29         }
30         memset(r,0,sizeof(r));
31         memset(c,0,sizeof(c));
32         int ans=0;
33         //x 和 y枚举最大和矩阵的左上角在第一个小矩阵中的位置
34         for (int x=1 ;x<=n ;x++)
35         {
36             for (int y=1 ;y<=n ;y++)
37             {
38                 for (int j=0 ;j<n ;j++)
39                 {
40                     for (int i=0 ;i<n ;i++)
41                     {
42                         c[i]=an[x+i][y+j];
43                         if (i) c[i] += c[i-1];
44                         if (!j) r[i]=c[i];
45                         else r[i] += c[i];
46 
47                         if (r[i]>ans) ans=r[i];
48                     }
49                 }
50             }
51         }
52         printf("%d
",ans);
53     }
54     return 0;
55 }