b232 - TOI2009 第四題：分房子

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算將 N 間房子分給朋友的方法數，其中每次分房子的數量必須是奇數。例如，如果 N=5，則有效的分法有 5, 3+1+1, 1+1+1+1+1。題目給定 M 組測試資料，每組資料包含一個正整數 N，要求輸出 N 的有效分法數量。

解題思路

這題可以使用動態規劃來解決。ans[i] 表示將 i 間房子分給朋友的有效分法數量。初始化 ans[0] = 1 (代表沒有房子時只有一種分法，即不分)。然後，對於每個 i 從 1 到 750，我們考慮所有可能的奇數房屋分配方案。例如，如果我們分配了 1 間房子，則剩下 i-1 間房子，有 ans[i-1] 種分法。如果我們分配了 3 間房子，則剩下 i-3 間房子，有 ans[i-3] 種分法，以此類推。由於題目限制 N 最大為 750，因此可以使用陣列來儲存中間結果。

更具體地，ans[i] 可以通過以下方式計算： ans[i] = ans[i-1] + ans[i-3] + ans[i-5] + ... + ans[0] 其中，只有當 i-k >= 0 時，ans[i-k] 才有效。

程式碼中，迴圈 for(int i=1;i<=749;i+=2) 迭代所有可能的奇數分配數量。內部迴圈 for(int j=0;j+i<751;++j) 計算 ans[j+i] 的值，將 ans[j] 加到 ans[j+i] 上。

複雜度分析

• 時間複雜度: O(N^2) (外層迴圈執行約 N/2 次，內層迴圈執行約 N 次)
• 空間複雜度: O(N) (使用一個大小為 751 的陣列 ans 儲存中間結果)

程式碼

#include <iostream>
using namespace std;
long long int ans[751]={1},c,n;
int main(){
	for(int i=1;i<=749;i+=2){
		for(int j=0;j+i<751;++j){
			ans[j+i]+=ans[j];
		}
	}
	while(cin >> c){
		while(c--){
			cin >> n;	
			cout << ans[n] << "\n";
		}
	}
}