この問題では、往路と復路で同じガソリンスタンドを使うことができないという制約があるため往路と復路を独立に考えるのではなく、各ガソリンスタンドについて往路での挙動と復路での挙動を同時に考えることにより見通しがよくなります。

座標 \(X_i\) で往路では \(j\) リットル、復路では \(k\) リットルの燃料を持っているときに座標 \(X_1, X_2, \ldots, X_i\) で支払う金額の合計の最小値を \(dp_{i,j,k}\) とおきます。 ただし、座標 \(X_i\) のガソリンスタンドを使用する場合、往路においては使用した後の値、復路においては使用する前の値で \(j, k\) を定めます。

本問題の答えは \(j = 0,1, \ldots, H\) に対する \(dp_{N,j,j}\) の最小値であることに注意してください。

座標 \(X_i\) で燃料を持っている量がわかるとき、座標 \(X_{i+1}\) で持っている燃料の量は簡単に求めることができます。
具体的には、以下の \(4\) つに注意してください。

• 往路において座標 \(X_i\) で燃料を \(j\) リットル持っているとき、\(j \geq X_{i+1} - X_i\) ならば 座標 \(X_{i+1}\) で持っている燃料の量は \(j - (X_{i+1} - X_i)\) リットルとなる。\(j < X_{i+1} - X_i\) ならば、座標 \(X_{i+1}\) にたどり着くことはできない。

• 復路において座標 \(X_i\) で燃料を \(k\) リットル持っているとき、\(k + X_{i+1} - X_i \leq H\) ならば座標 \(X_{i+1}\) で持っている燃料の量は \(k + X_{i+1} - X_i\) リットルである。\(k+ X_{i+1} - X_i > H\) ならば、座標 \(X_i\) で燃料を \(k\) リットル持っていることはそもそもあり得なかったとわかる。

• 往路において座標 \(X_i\) に存在するガソリンスタンドを使う前に燃料を \(j\) リットル持っているとき、ガソリンスタンドを使った後に持っている燃料の量は \(\min(j+F_i,H)\) リットルとなる。

• 復路において座標 \(X_i\) に存在するガソリンスタンドを使った後に燃料を \(k\) リットル持っているとき、ガソリンスタンドを使う前に燃料を持っている量としてありえるものは \(k = H\) のとき \(k - F_i\) リットル以上 \(k\) リットル以下のいずれか、\(F_i \leq k < H\) のとき \(k - F_i\) リットルである。

上で示した事実に注意して dp を行うことで、答えを \(O(NH^2)\) の時間計算量で得ることができます。