24h購物| | PChome| 登入
2011-06-10 19:43:48| 人氣3,533| 回應0 | 上一篇 | 下一篇

d904. 換零錢

推薦 0 收藏 0 轉貼0 訂閱站台

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

提示 :

出處 :

USACO 2007 January Competition (管理:B88000005)

作法 : DP

/**********************************************************************************/
/*  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;
}

台長: Morris
人氣(3,533) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:d899. NOIP2010 1.数字统计

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文