題目描述

母牛們不但創建了他們自己的政府而且選擇了建立了自己的貨幣系統。
[In their own rebellious way],，他們對貨幣的數值感到好奇。
傳統地，一個貨幣系統是由1,5,10,20 或 25,50, 和 100的單位面值組成的。
母牛想知道有多少種不同的方法來用貨幣系統中的貨幣來構造一個確定的數值。
舉例來說, 使用一個貨幣系統 {1,2,5,10,...}產生 18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。
寫一個程序來計算有多少種方法用給定的貨幣系統來構造一定數量的面值。
保證總數將會適合long long (C/C++) 和 Int64 (Free Pascal)。

輸入

輸入包含多組測試數據

?

貨幣系統中貨幣的種類數目是 V 。 (1<= V<=25)
要構造的數量錢是 N 。 (1<= N<=10,000)

第 1 行:	?二整數， V 和 N
第 2 ..V+1行：	可用的貨幣 V 個整數　(每行一個　每行沒有其它的數)。

?

輸出

單獨的一行包含那個可能的構造的方案數。

樣例輸入

3 10 1 2 5

樣例輸出

10 #include <iostream> #include <algorithm> using namespace std;typedef long long ll; const int maxn = 10000+10; int V, N; //貨幣種類數，數量錢 int vv[maxn]; ll dp[maxn];int main() {while(~scanf("%d%d", &V, &N)){for(int i = 0; i < V; i++){scanf("%d", &vv[i]);}sort(vv, vv+V);for(int i = 0; i <= N; i++){dp[i] = 0;}dp[0] = 1;for(int i = 0; i < V; i++){for(int v = vv[i]; v <= N; v++){dp[v]=dp[v]+dp[v-vv[i]];}}printf("%lld\n", dp[N]);}return 0; }

?

總結

以上是生活随笔為你收集整理的Codeup-问题 C: 货币系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。