グラフ理論が苦手な気がしてきたのでさっと組み合わせ最適化をおさらいすることにした． 実はDinicとか強連結成分分解とか今まで1回も書いたことないのでそろそろ書いておいた方がいい気がしてきた． 2章 グラフ 定義がいっぱい 命題2.2 グラフG，X⊆V(G)に対…

寝起きにぼけっと考えていた． 縦 | 横 に切ると，再び長方形になる． dp[y][x]や，dp[line][y]といったタイプの動的計画法に帰着しやすい． 面積=縦×横． 各マスに数字を書いたとき，その部分長方形の総和を，下準備O(W*H)の後でO(1)で求められる． さらに…