色々実験して性質を観察するの大事・・・ 問題 atcoder.jp 解法 とりあえず頂点数が小さい範囲でどのような向き付けができるかを見てみる． すると任意の２頂点u,vに対して u→vの向きづけがあるならば，c[u]>=c[v] が成り立っていることがわかる． あとは，…

問題 atcoder.jp 解法 問題のタイトル通りナップザック問題を考える． dp[i][j]:i番目までの要素までを用いた部分集合Sを考えたとき，総和がjになるようなSの部分集合の数 とすると，dp[n][s]が答えとなる． すると，遷移としては以下が考えられる． （要素a…