解説https://atcoder.jp/contests/dp/submissions/3980762動的計画法で困るのが、順番が任意である場合である。場合によっては最適な順番があり、固定できる場合がある。i番目までを使って、重さの総和がtotである場合の価値の総和の最大値とDPを立てることができ、更新も使う使わないの2通りなので、解ける。最適な順番にソートできないか考えてみる。C++なら大体sort関数を作るが、これはある2項について考えるものであり、ソートしてからDPする場合は大体2項について考えればいい。ブロックaとブロックbのどちらが上の方がいいかの判定を考える。S[a]-W[b])をみたせばいい。これでソートして、DPする。B]月別アーカイブスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。