#52: 題解


Ching367436 (Ching367436)

School : 一中
ID : 41
IP address : [172.68.62.162]
Last Login :
2021-04-08 09:15:31
c039. VIII. 點點的$零錢$ -- 臺中一中電腦資訊研習社 | From: [141.101.105.8] | Post Date : 2021-01-28 10:33

令 $dp[i][j]$ 表到第 $i$ 種面額, 湊成 $j$ 元的最大零錢個數

$dp[i+1][j] = max(dp[i][j-a_i], dp[i][j])$

答案為

$dp[n-1][p]$

可以用成一維dp (https://cses.fi/book/book.pdf 第73頁)

這樣可以拿到約 50%

 

如果把同種零錢分堆如下

$1, 2, 4, ..., 剩下的$

 

然後dp

可以全拿

 
ZeroJudge Forum