原題：
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.
樣例輸入：
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
樣例輸出：
15
45
思路與總結：
是上一題（UVa 108 - Maximum Sum）的再次升級版。情況變復雜了很多。這個矩陣是可以“循環轉動”的。例如，當所有行都上升一行，那麼第一行就會變成最後一行（原先第2行變成第1行，第3行變成第2行……）， 當所有行下降一行，最後一行就變成第一行。 同理，列也是循環的，把上一句話的所有“行“字變成”列“字就是列循環的情況。
怎樣處理這種情況呢？
如果之前做過什麼涉及到圓環啊之類的題目，那麼肯定馬上會想到把在原數組後面再增加重復一遍這個數列的數。 例如1，2，3，4， 處理後變成1，2，3，4，1，2，3。 那麼這個新序列就可以枚舉圓環出所有的連續序列。
同理，這題需要擴大增加這個矩陣， 把這個存這個矩陣數字的數組的每一行增加一倍， 重復一遍數字， 每一列也增加一倍重復一遍。最後形成一個新的2N*2N的大矩陣。
然後再在這個新的大矩陣中找到尺寸小於等於N*N的子矩陣的最大和。
由於增加了一個限制：子矩陣的尺寸要小於等於N*N， 那麼在進行求“最大連續和”的過程時， 要進行線性掃描，這裡需要用到單調隊列的應用（以前做過一道單調隊列求最大連續和長度有限制的題：Max Sum of Max-K-sub-sequence)。單調隊列的用處就是維護一個長度小於N的最小值。
代碼：
[cpp]
/*
* UVa: 10827 - Maximum sum on a torus
* Time: 0.236s
* Author: D_Double
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 250
using namespace std;
struct Node{
int val; // 值
int no; // 下標
};
int arr[MAXN][MAXN], sum[MAXN][MAXN], N, ans;
inline void input(){
memset(arr, 0, sizeof(arr));
memset(sum, 0, sizeof(sum));
for(int i=1; i<=N; ++i){
for(int j=1; j<=N; ++j)
scanf("%d", &arr[i][j]);
for(int j=N+1; j<2*N; ++j)
arr[i][j]=arr[i][j-N];
}
for(int i=N+1; i<2*N; ++i){
for(int j=1; j<2*N; ++j)
arr[i][j] = arr[i-N][j];
}
// 轉化
for(int i=1; i<2*N; ++i){
for(int j=1; j<2*N; ++j)
sum[i][j] = arr[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
}
}
inline void solve(){
deque<Node>que;
Node temp;
int maxSum=-2147483646;
for(int i=1; i<2*N; ++i){
for(int j=(i-N>=0?i-N:0) ; j<i; ++j){ // 枚舉
que.clear(); // 記住要清空！！
int prev=0;
for(int k=1; k<2*N; ++k){
// 維護單調隊列
while(!que.empty() && que.back().val > prev)
que.pop_back();
while(!que.empty() && que.front().no < k-N)
que.pop_front();
temp.val=prev, temp.no=k-1;
que.push_back(temp);
int val=sum[i][k]-sum[j][k]-que.front().val;
if(val>maxSum) maxSum=val;
prev = sum[i][k]-sum[j][k];
}
}
}
printf("%d\n", maxSum);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
input();
solve();
}
}
作者：shuangde800
