程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 10755 - Garbage Heap（三維子矩陣最大和）

UVA 10755 - Garbage Heap（三維子矩陣最大和）

編輯：C++入門知識

Garbage Heap

Time limit: ? seconds Memory limit: 64 megabytes

Farmer John has a heap of garbage formed in a rectangular parallelepiped.

It consists of $A\times B\times C$ garbage pieces each of which has a value. The value of a piece may be 0, if the piece is neither profitable nor harmful, and may be negative which means that the piece is not just unprofitable, but even harmful (for environment).

The farmer thinks that he has too much harmful garbage, so he wants to decrease the heap size, leaving a rectangular nonempty parallelepiped of smaller size cut of the original heap to maximize the sum of the values of the garbage pieces in it. You have to find the optimal parallelepiped value. (Actually, if any smaller parallelepiped has value less than the original one, the farmer will leave the original parallelepiped).

<喎?http://www.BkJia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPGgyPklucHV0PC9oMj4KPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgdGhlIHRlc3QgY2FzZXMsIHdoaWNoIGlzIGF0IG1vc3QgMTUuIFRoZSBkZXNjcmlwdGlvbnMgb2YgdGhlIHRlc3QgY2FzZXMgZm9sbG93LiBUaGUgZmlyc3QgbGluZSBvZiBhIHRlc3QgY2FzZSBkZXNjcmlwdGlvbiBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBBLCBCLAogYW5kIEMgKDEgodwgQSwgQiwgQyCh3CAyMCkuIFRoZSBuZXh0IGxpbmVzIGNvbnRhaW4gPGltZyBjbGFzcz0="mathimg" src="http://www.bkjia.com/uploads/allimg/140122/154Z210c-2.png" alt="$A\cdot B\cdot C$" width="67" height="13"> numbers, which are the values of garbage pieces. Each number does not exceed $2^{31}$ by absolute value. If we introduce coordinates in the parallelepiped such that the cell in one corner is (1,1,1) and the cell in the opposite corner is (A,B,C), then the values are listed in the order

$\begin{gathered}(1,1,1),(1,1,2),\dots,(1,1,C),\\(1,2,1),\dots,(1,2,C),\dots,(1,B,C),\\(2,1,1),\dots,(2,B,C),\dots,(A,B,C).\end{gathered}$

The test cases are separated by blank lines.

Output

For each test case in the input, output a single integer denoting the maximal value of the new garbage heap. Print a blank line between test cases.

Examples

Input Output

1

2 2 2
-1 2 0 -3 -2 -1 1 5

題意：說白了求三維子矩陣最大和。

思路：利用前綴和的思想求出2維每個子矩陣和，剩下就等同於求一維子序列最大和的方法一樣了。

代碼：

#include 
#include 
#define max(a, b) (a)>(b)?(a):(b)
#define INF 0x3f3f3f3f3f3f3f
const int N = 25;

int t, A, B, C;
long long g[N][N][N], sum[N][N][N][N], res[N][N][N][N];

void init() {
	scanf("%d%d%d", &A, &B, &C);
	for (int i = 1; i <= A; i++)
		for (int j = 1; j <= B; j++)
			for (int k = 1; k <= C; k++)
				scanf("%lld", &g[i][j][k]);
}

long long solve() {
	long long ans = -INF;
	for (int c = 1; c <= A; c++) {
		for (int i = 1; i <= B; i++) {
			for (int j = i; j <= B; j++) {
				for (int k = 1; k <= C; k++) {
					long long h = 0;
					for (int l = k; l <= C; l++) {
						h += g[c][j][l];
						sum[i][j][k][l] = sum[i][j - 1][k][l] + h;
						if (c == 1) res[i][j][k][l] = sum[i][j][k][l];
						else res[i][j][k][l] = max(sum[i][j][k][l], res[i][j][k][l] + sum[i][j][k][l]);
						ans = max(ans, res[i][j][k][l]);
					}
				}
			}
		}
	}
	return ans;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		init();
		printf("%lld\n", solve());
		if (t) printf("\n");
	}
	return 0;
}