UVa 10727-Maximsum on a tors

テーマリンク:
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=113&page=show_problem&problem=1768
原題:
A grid a that wraps both horizontally and verticalllys s caled a tototous.Gven a totous whehehererererererererererereem.determine the sub-rectangle with the largest sum.The sum of sum of a sub-sub-rectanleles thethetherererererererectles s s s s s s s s s s s s s thethethetherererereininininininininininininininininininininininininrererererererererererererererererererererererererererererererererererehas been sharded.
 
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.Each case starts with an integer N(1≦N≦75)specifying the size of the tors(always square).The n follows N deright ingnese.ingtoring.The
 
Output
For each test case、output a line containing a single integer：the maximm sum of a sub-rectangle within the tors.
サンプル入力：

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行下がると、最後の行が1行目になります。 同じように、列も循環しています。前の文のすべての行を「字」の列「字」に変えるのが列循環の場合です。
このような状況をどう処理しますか？ 
前に何をしましたか？円環とかの問題があったら、すぐに元の配列の後ろにもう一度この数列の数を増やしたいと思います。例えば1、2、3、4、 処理後は1、2、3、4、1、2、3になります。 この新しいシーケンスは、すべての連続シーケンスを円環で列挙することができます。
同じように、この問題はこの行列を拡大して増加させ、この行列の数字を保持する配列の各行を倍にして、数字を繰り返し、各列も倍にして繰り返します。最後に新しい2 N＊2 Nの大きな行列が形成される。
次に、この新しい大きな行列において、N＊N以下のサイズのサブ行列の最大和を見出した。
一つの制限が追加されました。サブマトリックスのサイズはN＊N以下になります。「最大連続和」を求める過程で、線形スキャンを行います。ここでは単調行列の応用が必要です。単調なキューの役割は、長さがNより小さい最小値を維持することである。
コード:

/*
 * 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
", maxSum);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        input();
        solve();
    }
}

——       ，       。
  
   
  
  
  

    
   
   
             
   
  
  
  
   
  
  
  

    
   
   
           http://blog.csdn.net/shuangde800 ， By   D_Double  (     )