2011-06-10 19:43:48Morris
d904. 換零錢
http://zerojudge.tw/ShowProblem?problemid=d904
內容 :
可憐的貝茜在Slobbovia邊境的便利商店工作。Slobbovian國的人使用不同與美國不同的幣值,而且幣值隨時在更動!
請你幫助貝茜做出最佳情況硬幣數給Slobbovian顧客。你需要用N(1<=N<=10)種不同的硬幣數提供C(1<=C<=1000)美分給顧客。你可以假設所有的測資都是可以用此N種硬幣提供出來的。
舉例:如果有5種不同的幣值50,25,10,5,1可用,貝茜將找出93美分的最佳情況硬幣數(最少的硬幣),用1個50,1個25,1個10,1個5,3個1的硬幣(共7個硬幣)為最佳硬幣數。
那能有多難呢?最後兩個測資較具有挑戰性。
輸入說明
:
每筆測資的第1行有兩數字C與N,其中用一個空格隔開 接下來的第2到第N+1行為各種不同的幣值
輸出說明
:
輸出最佳情況硬幣數
範例輸入 :
93 5 25 50 10 1 5
範例輸出 :
7
提示
:
出處
:
/* Problem: d904 "換零錢" from USACO 2007 January Competition */
/* Language: C */
/* Result: AC (2ms, 254KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-04 21:59:35 */
/**********************************************************************************/
#include<stdio.h>
main() {
int a, b, c, n;
while(scanf("%d %d", &c, &n) == 2) {
int DP[1001] = {}, money[10];
for(a = 0; a < n; a++) scanf("%d", &money[a]);
for(a = 0; a <= c; a++)
for(b = 0; b < n; b++)
if(a + money[b] <= c) {
if(DP[a + money[b]] == 0) {
if(a == 0)
DP[a + money[b]] = 1;
else
DP[a + money[b]] = DP[a] + 1;
}
else if(DP[a + money[b]] > DP[a] + 1)
DP[a + money[b]] = DP[a] + 1;
}
printf("%d\n", DP[c]);
}
return 0;
}