UVA 147 - Dollars

UVA 147 - Dollars

題目概述:

就很基礎的硬幣問題。給很多種幣值，求某種金額可以用幾種方法來組成。

思路:

就DP吧!可以轉成無限背包問題。狀態dp[i]定為組成金額i有多少種組合。轉移的話應該看code就清楚了。

AC code:

//By SCJ

//uva 147

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define maxn 30000

long long dp[maxn+5]={1},a[11]={10000,5000,2000,1000,500,200,100,50,20,10,5};

int main()

{

for(int i=0;i<11;++i)

for(int j=a[i];j<=maxn;++j)

dp[j]+=dp[j-a[i]];

double x;

while(cin>>x)

{

if(x==0) break;

int tp=x*100;

if(tp%5==4) tp++;

else if(tp%5==1) tp--;

printf("%6.2lf%17lld\n",x,dp[tp]);

}

}