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

 

 

這題超級重要啊@@ 

, , ,
創作者介紹

Tube's World

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


留言列表 (1)

發表留言
  • zxc10806
  • 來寫寫看好了XD