考察
右/下へ一歩進むたびi+jが1増えるため、cell(i,j)を訪れる日はpathによらずi+j-1日目に固定される。B_{i,j}=A_{i,j}-P_{i+j-1} とすれば各cell到着時の所持金変化になり、必要なのは全prefix所持金を非負にできるright/down pathと最小初期額である。dpは現在cellでcoinsを回収・食費を払う前の額なので、現在のnet Bを得た後に次cellの必要額を満たす条件はcash≥nextNeed-Bである。必要額は非負に制限されるためBが十分正なら0でよい。grid外の遷移を∞とすればedge/cornerも同じ式で処理できる。
採用する候補: dp[i][j]をcell到着直前に必要な最小所持金としてgoalから逆向きに計算する
次cellへ必要な額の小さい方を選び、現在の純増Bを差し引いて0未満をclampすれば dp=max(0,min(down,right)-B)。局所最適が将来必要額を完全に表す。
棄却する候補: 初期額xをbinary searchし、各xについて到達可能cellと最大残金をforward DPする
判定一回O(HW)にさらにlog answerが掛かり、必要資金を逆算すれば一回のDPで厳密値が得られる。
必要額は非負に制限されるためBが十分正なら0でよい。
各cellのB=A-P_{i+j-1}を計算する。i=H..1,j=W..1の逆順で、goalはmax(0,-B)、他はmax(0,min(dp[i+1][j],dp[i][j+1])-B)とする。dp[1][1]を出力し、rolling rowでもO(W) memoryにできる。
典型の発動条件
必要資源の逆向きDP
発動条件: 各地点で資源が増減し、終点までprefix非負にする最小開始資源を求めるとき。
後続の必要額から現在の純増を引き、0でclampして逆算する。
時刻の座標不変量
発動条件: monotone grid pathでevent costがstep番号に依存するとき。
i+j-1が訪問日と固定されることからcell weightへ日別costを埋め込む。
問題固有の要素
日ごとの食費をpath状態として持たず、monotone移動の対角線番号へ吸収すると、通常のweighted grid DPになる。
別の問題へ持ち帰る視点: step依存costがある格子路では、全pathが同じ座標へ同じstepで着くrank関数がないか先に調べる。
正当性
dpはそのマスへ入る前に必要な最小所持金。後続へ必要額はdown/rightの小さい方で、その額から現在純増Bを引く。所持金非負条件を加えてmax(0,need−B)。どの額もこの最小以上なら同じ将来pathが可能なので局所最小が十分。
実装上の注意
- goalでもその日の回収後にPを払うためmax(0,-B_goal)が必要。差と累積必要額は64 bitを使い、H=1またはW=1の唯一pathも扱う。
復習の核
- 1×1、全B正、最初に大赤字後で黒字、二pathで最終利益とprefix不足が逆転する例を全pathのprefix和と比較する。
計算量と制約
時間
H×Wマス。逆順DP O(HW)。
空間
rolling row O(W)、入力A保持なら O(HW)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: H,W\geq 1; H\times W \leq 2\times 10^5; 1\leq A_{i,j}\leq 10^9; 1\leq P_k\leq 10^9; All input values are integers.
出典