UVa 108 Maximum Sum

解題策略

這題AC的關鍵是時間，用暴力法O(n⁶) 六層迴圈去解鐵定超時。已知最佳的解法是 O(n³) ，不過一般用O(n⁴) 就可以通過了。

我也是用 O(n⁴) 的解法，首先用四層迴圈窮舉子矩陣的左上角(x1,y1) 跟右下角 (x2,y2) 的位置，一旦給定了子矩陣後，就要 O(1) 時間得到子矩陣的和。

要達成這個目標可以透過 sum table 來達成，我說明一下我的方法， sum table ( i, j ) 每個位置儲存的值的是原矩陣 (1,1) ~ (i, j) 之間的元素總和。像下圖的 sum table ( 2, 3 ) 的值就是 原矩陣 (1, 1) ~ (2, 3) 之間的元素和。

一旦建好 sum table，那接下來就可以簡單透過這 D - B -C + A 這四個sum table的元素直接得到子矩陣的和了。

閒聊

最後執行時間0.052 過關....改天再將作法補完，我好睏....晚安。原本用暴力法去跑 100x100 的矩陣，竟然要253秒(大汗)。

	/**
	* UVa 108 Maximum Sum
	* Author: chchwy
	* Last Modified: 2011.10.08
	* Tag: Dynamic Programming
	*/
	#include<cstdio>
	#include<cstring>
	#include<climits>
	enum { MAX_DIM = 100 + 1 };
	int subMatrixSum(int sumTable[][MAX_DIM], int x1, int y1, int x2, int y2)
	{
	int sum = sumTable[x2][y2]
	- sumTable[x1 - 1][y2]
	- sumTable[x2][y1 - 1]
	+ sumTable[x1 - 1][y1 - 1];
	return sum;
	}
	int main()
	{
	int dimension; //the dimension of matrix
	int sumTable[MAX_DIM][MAX_DIM];
	while (scanf("%d", &dimension) == 1)
	{
	memset(sumTable, 0, sizeof(sumTable));
	// Build Sum Table
	for (int i = 1; i <= dimension; ++i)
	{
	for (int j = 1; j <= dimension; ++j)
	{
	int value;
	scanf("%d", &value);
	sumTable[i][j] = sumTable[i - 1][j]
	+ sumTable[i][j - 1]
	- sumTable[i - 1][j - 1]
	+ value;
	}
	}
	int max_sum = INT_MIN;
	//position (x1,y1)
	for (int x1 = 1; x1 <= dimension; ++x1)
	{
	for (int y1 = 1; y1 <= dimension; ++y1)
	{
	//position (x2,y2)
	for (int x2 = x1; x2 <= dimension; ++x2)
	{
	for (int y2 = y1; y2 <= dimension; ++y2)
	{
	int sum = subMatrixSum(sumTable, x1, y1, x2, y2);
	if (sum > max_sum)
	max_sum = sum;
	}
	}
	}
	}
	printf("%d\n", max_sum);
	}
	return 0;
	}

view raw 108.cpp hosted with ❤ by GitHub