題目描述

在創(chuàng)立了她們自己的政權(quán)之后，奶牛們決定推廣新的貨幣系統(tǒng)。在強烈的叛逆心理的驅(qū)使下，她們準備使用奇怪的面值。在傳統(tǒng)的貨幣系統(tǒng)中，硬幣的面值通常是1，5，10，20或25，50，以及100單位的貨幣，有時為了更方便地交易，會發(fā)行面值為2單位的硬幣。 奶牛們想知道，對于一個給定的貨幣系統(tǒng)，如果需要正好湊出一定數(shù)量的錢，會有多少種不同的方法。比如說，你手上有無限多個面值為{1，2，5，10，...}的硬幣，并且打算湊出18單位貨幣，那么你有多種方法來達到你的目的：18*1，9*2，8*2+2*1，3*5+2+1，以及其他的未列出的若干方案。 請你寫一個程序，幫奶牛們計算一下，如果想用有V (1 <= V <= 25)種面值的硬幣，湊出總價值為N(1 <= N <= 10,000)的一堆錢，一共有多少種不同的方法。答案保證不會超出C/C++中的'long long'，Pascal中的'Int64'，或是Java中的'long'的范圍。

輸入

* 第1行: 2個用空格隔開的整數(shù)：V和N

* 第2..V+1行: 每行1個整數(shù)，表示1種硬幣面值

輸出

* 第1行: 輸出1個正整數(shù)，表示用這V種面值的硬幣，湊出N單位的貨幣的不同方法總數(shù)。

樣例輸入

3 10
1
2
5

樣例輸出

10

---

題解

完全背包水題，沒啥要注意的

#include <cstdio> long long f[10001]; int main() {int v , n , i , t;scanf("%d%d" , &v , &n);f[0] = 1;while(v -- ){scanf("%d" , &t);for(i = t ; i <= n ; i ++ )f[i] += f[i - t];}printf("%lld\n" , f[n]);return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的【bzoj1708】[USACO2007 Oct]Money奶牛的硬币 背包dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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