O(2^n)から計算量を減らす問題
O(2^n)から計算量を減らす問題 - けんちょんの競プロ精進記録
DP
現在の選択が遠い未来にまで直接的には影響を及ぼさない
予めn個のモノをソート
ナップサック問題
重み付き区間スケジューリング問題
連立1次方程式
https://archive.org/search.php?query=http%3A%2F%2Ftopcoder.g.hatena.ne.jp%2Fpepsin-amylase%2F20131203
ライツアウト系
最小カット
最大独立集合問題
フローに帰着するパターン
二部グラフ上の最大独立集合問題
頂点数 - 二部グラフの最大マッチング
推移率を満たすDAG上の最大独立集合問題
Dilworthの定理により「DAG最小パス被覆」に等しい
区間グラフ上の最大独立集合問題
区間スケジューリング
パス上の最大独立集合問題
ツリー上の最大独立集合問題
推移閉包を取った有向ツリー上の最大独立集合問題
貪欲法
区間スケジューリング問題
マトロイド
最短路問題
最小カット問題
マトロイド交差問題
2つのマトロイド(E, F1), (E, F2)があったとき、$ F1 \cap F2 での最大化
二部グラフの最大マッチング問題
有向全域木問題
カラフル全域木問題
全域木をパッキングする問題
指数時間アルゴリズム入門