AtCoder 復習用 動的計画法 (DP) 編
自分の復習用に AtCoder の動的計画法 (DP) の問題を雑に並べています。
- 動的計画法 (DP) 以外の問題を雑に並べている記事
いつも読む
大変お世話になっております。
テーマ別
未分類
- そもそも
- 問題 : EDPC A - Frog 1
- 問題 : ABC 129 C - Typical Stairs
- 問題 : EDPC B - Frog 2
- 問題 : ABC 099 C - Strange Bank
- 問題 : EDPC C - Vacation
- 問題 : ABC 113 D - Number of Amidakuji
- 問題 : EDPC G - Longest Path
- 問題 : EDPC H - Grid 1
- 問題 : ABC 044 C - 高橋君とカード
- 問題 : EDPC I - Coins
- 問題 : EDPC K - Stones
- 問題 : EDPC M - Candies
- 問題 : 天下一プログラマーコンテスト2014予選B B - エターナルスタティックファイナル
- 問題 : ABC 037 D - 経路
- 問題 : ABC 122 D - We Like AGC
- 問題 : ABC 141 E - Who Says a Pun?
- 問題 : ABC 078 D - ABS
ナップサック DP
- そもそも
- 問題 : EDPC D - Knapsack 1
- ナップサックに入れてもよい品物が 番目までのとき、容量 のナップサックで実現可能な価値の総和の最大値
- 番目の品物の重さを 、価値を とする。 番目の品物を入れるならば で、 番目の品物を入れないならば で、このうち大きい方を の値とする
- 問題 : EDPC E - Knapsack 2
- ナップサックに入れてもよい品物が 番目までのとき、価値の総和が となるように品物を選んだときの重さの総和の最小値
- 番目の品物を入れるならば で、 番目の品物を入れないならば で、このうち小さい方を の値とする
- 問題 : ABC 153 E - Crested Ibis vs Monster
- 個数制限なしナップサック問題
- 問題 : ABC 015 D - 高橋くんの苦悩
- 問題 : ABC 145 E - All-you-can-eat
最長共通部分列 (LCS)
- そもそも
- 文字列 は先頭 から まで、文字列 は先頭 から までを注目したときの LCS 長
- のとき で、 のとき
- 問題 : EDPC F - LCS
- 問題 : CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除
区間 DP
- そもそも
- 問題 : EDPC L - Deque
- 問題 : EDPC N - Slimes
- 問題 : JOI 2014/2015 本選 B - ケーキの切り分け2 (Cake 2)
bit DP
- そもそも
- 問題 : EDPC O - Matching
- 問題 : ABC 142 E - Get Everything
- 問題 : 第一回 アルゴリズム実技検定 I - 部品調達 / Procurement
木 DP
- 問題 : EDPC P - Independent Set
- 問題 : ABC 036 D - 塗り絵
- EDPC P - Independent Set と全く同じ
最長増加部分列 (LIS)
- そもそも
- 問題 : EDPC Q - Flowers