P1474 貨幣系統(tǒng) Money Systems

題目描述

母牛們不但創(chuàng)建了它們自己的政府而且選擇了建立了自己的貨幣系統(tǒng)。由于它們特殊的思考方式，它們對(duì)貨幣的數(shù)值感到好奇。

傳統(tǒng)地，一個(gè)貨幣系統(tǒng)是由1,5,10,20 或 25,50, 和 100的單位面值組成的。

母牛想知道有多少種不同的方法來用貨幣系統(tǒng)中的貨幣來構(gòu)造一個(gè)確定的數(shù)值。

舉例來說, 使用一個(gè)貨幣系統(tǒng) {1,2,5,10,...}產(chǎn)生 18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。 寫一個(gè)程序來計(jì)算有多少種方法用給定的貨幣系統(tǒng)來構(gòu)造一定數(shù)量的面值。保證總數(shù)將會(huì)適合long long (C/C++) 和 Int64 (Free Pascal)，即在0 到2^63-1之間。

輸入輸出格式

輸入格式：

貨幣系統(tǒng)中貨幣的種類數(shù)目是 V (1<=V<=25)。要構(gòu)造的數(shù)量錢是 N (1<= N<=10,000)。

第一行: 二個(gè)整數(shù)，V 和 N 。

第二行： 可用的貨幣的面值 。

輸出格式:

輸出格式：

單獨(dú)的一行包含那個(gè)可能的用這v種硬幣湊足n單位貨幣的方案數(shù)。

輸入輸出樣例

輸入樣例#1：
3 10 1 2 5 輸出樣例#1：
10

說明

翻譯來自NOCOW

USACO 2.3

?

與砝碼稱重相似：http://www.cnblogs.com/huibixiaoxing/p/6723080.html

完全背包計(jì)數(shù)。注意long long

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm>inline int read() {int x = 0;char ch = getchar();char c = ch;while(ch >'9' || ch < '0')c = ch,ch = getchar();while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0',ch = getchar();if(c == '-')return -1 * x;return x; }const int INF = 999999999; const int MAXN = 10000 + 10; const int MAXV = 25 + 5;long long w[MAXV]; long long f[MAXN]; long long v,n;int main() {v = read();n = read();for(int i = 1;i <= v;i ++){w[i] = read();}f[0] = 1;for(long long i = 1;i <= v;i ++){for(long long j = w[i];j <=n;j ++){f[j] += f[j - w[i]];}}std::cout<<f[n];return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/huibixiaoxing/p/6728509.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P1474 [USACO 2.3]货币系统 Money Systems [2017年4月计划 动态规划04]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。