問題概要
N階のダンジョンがあって、各階で消費する体力とコスト1で回復できる体力が決まっていて、Hを超えない。体力を常に1以上に保ったまま最下層まで行くのにかかる最小コストを求めよ。
小課題1
愚直DPをすると解ける。階数、残り体力を頂点として、コストの最小値を持つ。
体力を減らして下の階に行く重み0の辺と、体力を一定量増やす重み1の辺があって、計算量はO(NH)
アホをするとO(NH^2)になって解けない
小課題2
分からない
小課題3
愚直DPを重み0の辺のみで結ばれた頂点を同一視して考えると、一直線のDAGになる。
冷静に考えると体力は多ければ多いほど良いことが明らかであり、各頂点で最も遠い頂点に飛ぶべきだという貪欲が成り立つ。
シュミレーションしようと思ったときに、各頂点から飛べる最も遠い頂点を知りたい。
このDAGには各階で体力を（一定回復する、満タンにする）の2*N種類の辺があって、それぞれの種類が一つの区間の頂点から出ている。一発で辿り着ける頂点（＝満タンにする操作）のうち最も遠いものを一変数で、一定回復できる値の最大値をsetとかで持っておけば、並行処理O(NlogN)、クエリO(1)で飛べる最も遠い頂点が分かる。
回復が10^6回以内なので、NlogN+10^6くらいの計算で解ける。
小課題4(満点)
飛距離を決めているのはその頂点から出ている辺の種類であり、それが同じなら飛距離も同じである。辺の種類で区間を分けても区間は高々4*N個くらいなので、それぞれの区間ごとに最長の飛距離を求めて、次の区間に突入するまでの回数を割り算で求めてやると答えが求まる。今度はクエリが4*N回くらいしか呼ばれないので、NlogN+4*N程度の計算で解ける。
最初は何事かと思うが、貪欲が分かればやるだけ
