e656 - 11137 - Ingenuous Cubrency

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算使用立方數面額的硬幣支付給定金額 n 的方法數。硬幣面額為 1^3, 2^3, 3^3, ..., 21^3。

解題思路

本題為典型的找零問題，可以使用動態規劃 (Dynamic Programming) 解決。定義 dp[i] 為支付金額 i 的方法數。初始化 dp[0] = 1，表示支付金額 0 的方法數為 1 (不使用任何硬幣)。然後，遍歷所有可能的硬幣面額，對於每個硬幣面額 a[i]，更新 dp[j + a[i]] = dp[j + a[i]] + dp[j]，其中 j 從 0 到 n。最後，輸出 dp[n] 的值。由於題目要求計算不同順序的支付方式視為同一種，因此需要將 dp[n] 除以 2。

複雜度分析

• 時間複雜度: O(n * m)，其中 n 是目標金額，m 是硬幣種類的數量 (在本例中 m = 22)。
• 空間複雜度: O(n)，用於儲存 dp 陣列。

程式碼

#include <iostream>
using namespace std;
long long int a[22],n,dp[20001]={1};
int main(){
	for(int i=0;i<22;++i)
		a[i]=i*i*i;
	for(int i=22;i>0;--i)
		for(int j=0;j<=10000;++j)
			if(dp[j]!=0)
				dp[j+a[i]]+=dp[j];
	while(cin >> n)
		cout << dp[n]/2 << "\n";
}