題目: UVa - 10755 - Garbage Heap
題目說明
給一個 A
* B
* C
的長方體,長方體內每個單位都有數字,求最大的子長方體的數字和。
Input: 第一個整數為 T
,表示有 T
組測資,每組測資前三個整數依序為 A
、B
、C
,後面 A
* B
* C
個數字為長方體內單位的數字。
Output: 輸出最大的子長方體的數字和。
解題思路
Kadane’s Algorithm 題,依照二維壓成一維的概念將三維壓成二維,再將二維壓成一維之後使用 Kadane’s Algorithm 求解即可。
參考解法
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 79 80 81 82 83 84
| #include <bits/stdc++.h>
using namespace std;
static auto __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
int A, B, C; long long cuboid[21][21][21]; long long sum2D[21][21]; long long sum[21];
void read() { cin >> A >> B >> C; for (int i = 0; i < A; ++i) for (int j = 0; j < B; ++j) for (int k = 0; k < C; ++k) cin >> cuboid[i][j][k]; }
long long max1D() { long long mx, ret; mx = ret = sum[0];
for (int i = 1; i < C; ++i) { mx = max(mx + sum[i], sum[i]); ret = max(mx, ret); }
return ret; }
long long max2D() { long long mx = LLONG_MIN;
for (int i = 0; i < B; ++i) { for (int j = i; j < B; ++j) { for (int k = 0; k < C; ++k) sum[k] += sum2D[j][k]; mx = max(max1D(), mx); } memset(sum, 0, sizeof(sum)); }
return mx; }
void solve() { long long mx = LLONG_MIN; for (int i = 0; i < A; ++i) { for (int j = i; j < A; ++j) { for (int k = 0; k < B; ++k) for (int l = 0; l < C; ++l) sum2D[k][l] += cuboid[j][k][l]; mx = max(max2D(), mx); } memset(sum2D, 0, sizeof(sum2D)); }
cout << mx << '\n'; }
int main() { int T; cin >> T; while (T--) { read(); solve(); if (T) cout << '\n'; } }
|