UVA10827 - Maximum sum on a torus

UVA10827 - Maximum sum on a torus

題目鏈接

題意：給出一個環形矩陣，也就是第一行和最後一行是相連的，第一列和最後一列是相連的，求最大的子矩陣的和

思路：只要將矩陣復制四個，那麼就可以按照求一個矩陣內最大子矩陣之和的做法去做，即枚舉所有子矩陣的和，更新最大值。要注意在轉換後的大矩陣，枚舉的子矩陣規格是有范圍的。

代碼：

#include 
#include 
#include 
#include 

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 205;

int arr[MAXN][MAXN], sum[MAXN];
int n, Max;

int deal() {
    int temp;
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {
            memset(sum, 0, sizeof(sum)); 
            for (int k = i; k < i + n; k++) {
                temp = 0;     
                for (int l = j; l < j + n; l++) {
                    sum[l] += arr[k][l]; 
                    temp += sum[l];
                    if (Max < temp)
                        Max = temp;
                } 
            } 
        }
    }
    return Max;
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &n); 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) {  
                scanf("%d", &arr[i][j]);
                arr[i][j + n] = arr[i + n][j] = arr[i + n][j + n] = arr[i][j];
            }
        }
        Max = -INF;
        int ans = deal(); 
        printf("%d\n", ans);
    }
    return 0;
}