題目: UVa - 10827 - Maximum sum on a torus
題目說明 給一個 N
* N
的矩陣,矩陣上有一些數字,求最大的子矩陣和,子矩陣可跨過邊界。
Input: 第一個整數為 T
,表示有 T
組測資,每組測資第一個整數為 N
,後面 N
* N
個數字為矩陣中的數字。
Output: 求最大的子矩陣和,子矩陣可跨過邊界。
解題思路 Kadane’s Algorithm 題,將二維壓成一維之後使用 Kadane’s Algorithm 求解即可。
由於可跨過邊界,所以先將資料複製,將 N
* N
複製為 2N
* N
,第 N
列與第 0 列相同,第 N + 1
列與第 1 列相同,…。如此可解決跨越上下的情況,而跨左右的子矩陣可視為整個矩陣減去最小子矩陣。
參考解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include <bits/stdc++.h> using namespace std ;static auto __ = []{ ios_base::sync_with_stdio(0 ); cin .tie(0 ); cout .tie(0 ); return 0 ; }(); int N;int sum[76 ];int table[151 ][76 ];void read () { int tmp; cin >> N; for (int i = 0 ; i < N; ++i) for (int j = 0 ; j < N; ++j) { cin >> tmp; table[i][j] = table[i + N][j] = tmp; } } int max1D () { int mx, mxRet, mn, mnRet, total; mx = mxRet = mn = mnRet = total = sum[0 ]; for (int i = 1 ; i < N; ++i) { total += sum[i]; mx = max(mx + sum[i], sum[i]); mxRet = max(mx, mxRet); mn = min(mn + sum[i], sum[i]); mnRet = min(mn, mnRet); } if (total == mnRet) return mxRet; return max(mxRet, total - mnRet); } void solve () { int mx = INT_MIN; for (int t = 0 ; t < N; ++t) { for (int b = t; b < t + N; ++b) { for (int i = 0 ; i < N; ++i) sum[i] += table[b][i]; mx = max(max1D(), mx); } memset (sum, 0 , sizeof (sum)); } cout << mx << '\n' ; } int main () { int C; cin >> C; while (C--) { read(); solve(); } }
參考資料 UVa 10827 - Maximum sum on a torus | NaiveRed’s Blog