UVA 11401 - Triangle Counting

本題為中山大學高等程式設計課程作業指定題目之四星題。

題目大意

給予長度為 1, 2, …, n 的邊，問可以組成幾種三角形。

輸入範圍

3 <= n <= 1000000，n < 3 時結束。

解法

由於 1 + 2 <= 3，且 2 + 3 >= 4，可以知道第一個三角形會出現在 n = 4 的時候。

把 n 當作最大邊時，n - 1 當次大邊會有 n - 2 - 1 個邊能當第三邊，推廣到 n - 2, n - 3, … 3 當次大邊時的情形，會發現就是個等差級數和問題，可以直接 (a + b) * n / 2 求總和。

而每次都要尋找 n + n - 1 + … + 4 為最大邊的情形的話，在 n = 10^6 的情況下，效率過差，重複子問題其實符合 DP 的觀念: 前 k 個問題的解為前 k - 1 個問題的解的答案加上第 k 個問題的解。

程式碼

#include <iostream>
using namespace std;
const int maxi = 1000000 + 10;
long long dp[maxi];
int main() {
	dp[4] = 1;
	for(long long i=5; i<maxi; i++) {
		long long a = i - 3, b = i % 2 ? 0 : 1, n = (a - b) / 2 + 1;
		dp[i] = dp[i-1] + (a + b) * n / 2;
	}
	int n;
	while(cin >> n && n >= 3) {
		cout << dp[n] << endl;
	}
	return 0;
}