Educational DP Contest
ある目安として次のような基準があるらしい
入門A-D
初級E-I
中級J-S
上級T-Z
頂点を足場に対応させて、できるジャンプを全部辺として表現できる
$ dp\lbrack i \rbrack: $ i番目の足場に到達するまでの最短経路の重み
Frog 1とほぼ同じ
ただし、頂点の入次数が多いので、ある頂点から遷移前の頂点を見るときにfor文が必要
（std::max, minを効果的に使うと良さそう）
$ dp\lbrack i \rbrack: $ i番目の足場に到達するまでの最短経路の重み
DAGの経路を問題の高橋くんの過ごし方に対応させたい
Frog1と同じように対応づけるとちょっとややこしい
$ dp[i\rbrack: i日目に到達した地点での幸福度の最大値
こうすると、前日何をやったかが区別つかなくなる。
DAGではなくなる（現地点でできる遷移先が前の状態に依存する）
DAGに直すには、前の状態分の情報を頂点を持たせたい
$ dp[i\rbrack[j\rbrack: i日目に到達した地点で、その日に行動jを行った時の幸福度の最大値
このようにすれば、その頂点の状態だけから遷移先が決まる。
$ j \in \{A, B, C\}
頂点を(経過日数, その日に行った行動)に対応づける
辺をその日にできる行動分だけ伸ばし、伸ばした先は（次の日, 次の日に行った行動）とする。
こうすることで、最短経路問題に帰着できる
行動$ jをしている時に次の日は行動$ jはできないと言うプログラムは、次のようにして比較的楽に書けそう（重いけど）appbird.icon
code:cpp
(j != 0) ? happinessi-10 + hij : 0, (j != 1) ? happinessi-11 + hij : 0, (j != 2) ? happinessi-12 + hij : 0, });
ナップサック問題の解法は典型的だけど、あえて愚直に考えてみる。
そもそもこの問題は条件を満たす部分集合について最適化する問題
部分集合をどう分割してDAGに持っていくかが重要
非巡回グラフに変えるために ... 商品$ 0から$ nを順々に選んでいくように順序を定めると色々と取り扱いやすくなる。
同じ状態を2回巡ることはなくなるし
辿った経路によって遷移できる状態が変わることもない
dp[i]: 商品$ iまで考慮したときに重さを$ Wに抑えながら達成できる価値の最大値
これは高速に計算できるか？
dp[i]では商品iを選ぶか選ばないかを考慮すれば、dp[i-1]を用いて価値は高速に計算できる
しかし、ナップサックの重さはdp[i-1]からはわからない（解が実行可能解がどうかは不明） dpに重さを持たせると言う方式は考えられる
そうすると今度は最適性の定義がよくわからなくなる
価値, 重さについて$ (10, 5), (3, 3)という二つの状態があった時、後からの商品の選び方によっては$ (3, 3)が最適な経路になることは普通に考えられる
重ささえ記録されていて、各々の重さごとに経路が分かれていれば問題を解くのには十分appbird.icon
重さの分の情報はdp配列の引数の方に寄せて理解する。
dp[i][w]: 商品$ iまで考慮したときに重さを$ wにして達成できる価値の最大値
このようにすれば、重さの値を考慮しながら単純な最短経路問題として解ける 頂点は（考慮している商品の最大値, ナップサックの重み）として
辺はナップサックに商品$ iを入れる行為（重み$ v_i）か、入れないか（重み$ 0）の二通りの辺を引けば良い。
さて、今度は$ Wに沿ってDPするとオーバーフローするappbird.icon
$ W \leq 10^9
一方、品物の価値は大したことないので、これを手掛かりにDPをしたい。
まず、dp[i]では相変わらずダメ
dp[i]: 商品$ iまで考慮したときに重さを$ Wに抑えながら達成できる価値の最大値
相変わらず、重さがわからない。
ただ、重さを頂点の情報に載せるのはダメ
実行可能性と価値の情報がわかれば良い
重さをdpの値にして添字に価値の情報を載せても実行可能性の判別はできる。
dp[i][j]: 頂点$ iまで考慮したときに、価値を$ jにしながら達成できる重さの最小値
このようにすることで、実行可能解を全て列挙しながら、取り上げた解の中で実行可能なものが存在するかも調べられる
ここまで考えると、DP配列の引数（状態の列挙法）を決めるときに何を意識しているのかが少し見えてきた気がするappbird.icon
まず前提として、DP配列の引数一つ$ (i, j)は解全体集合の部分集合$ S_{i, j}に対応している DPとしての実行可能かの問題
1. $ S_{i, j}をDP配列の全ての引数にわたって集めた集合族は、実行可能領域を網羅できているか？ 2. $ S_{i,j}に含まれる解が、実行可能解であることが判定できるか？ つまり、初期状態$ S_0からある頂点$ S_{i,j}に到達するための最適なパス$ Pについて、
$ Pの部分路$ S_0 \to Sも$ Sへ到達するためのパスとして最適である。
このためには次の三つを意識すると良さそう
グラフになっているか？：ある頂点でできる遷移が経路に依存して変わらないか？ 実行可能か判定可能か？
計算量的な問題
4. $ |S|は巨大でないか？
5. 一頂点あたり辺の遷移は十分少ないか？
6. 実行可能性は高速に判定できるか？
あたりが重要そうで、まず1, 2, 3に注目すれば良さそう。