Q:http://uva.onlinejudge.org/external/3/357.html

經典的DP題

大意就是給你一個數字(0~30000)代表價格

這個價格可以用 1,5,10,25,50 這些價值的零錢來組合

問有多少種組合?

ex.  

11元 = 11個1元 = 1個5元+6個1元 = 2個5元+1個1元 = 1個10元+1個1元

可以看到11元的組合有4種,所以輸出就是4,以此類推

 

解法很單純,先令個陣列,大小超過30000,用來存組合數

接著透過DP將0~30000元的組合數算出來,之後就按照input輸出答案

要注意30000元的組合數過多,所以這個陣列要令成long long int

至於DP的演算法講解,可以參考以下網站:

http://www.tcgs.tc.edu.tw/~sagit/cpp/q12.htm

 

 

這題超級重要啊@@ 

arrow
arrow
    文章標籤
    ACM UVA 程式 DP
    全站熱搜

    Tube 發表在 痞客邦 留言(1) 人氣()