問題リンク この解法、結構時間かかるので流石に本番では選べないか……？ $N \leq 3000$ なので $Ο(N^2 log N)$ は通しにくい($Ο(N^3)$ でも枝刈すると通るらしいけど……)。 なるべく情報 $2$ 個で通らないだろうか？ 考えたこと $\frac{1}{2^i}$ を選ぶ部分和…

問題リンク 自分と同じ解法で通してる解説がなくて「？」になったのでやり方を書き残します。 とりあえず「組み合わせにおける個数」「組み合わせに含まれる品物の数」がわかればいいです。なので部分和 dp に個数の軸を加えて $dp[i][j][k]$ = $i - 1$ 番目…