No.015 D

動的計画法で解く.

$i$ 枚まで見たときに $j$ 枚貼り付けて幅が $k$ になったときの最大重要度を $A(i, j, k)$ とすると,

$$A(i, j, k) = \max(A(i-1, j, k), A(i-1, j-1, k-A_i) + B_i)$$

となる.