AOJ 2333 - Problem D: 僕の友達は小さい

問題リンク

Hyado君が解いていたので

解説

重さを昇順にして、としよう。

この時、

(絶対使うものは何もない) ]を作る

(は絶対使う) ]を作る

(は絶対使う) ]を作る

という風にしていけば、重複なく数え上げることができる。

区間の数え上げは重さを後述にみていけば自然とナップサック問題のDPで解くことができる。

計算量は

提出コード

onlinejudge.u-aizu.ac.jp

まとめ

最近Hyado君のsubmissionを追いがち？