DPのキーとして、公式解説で挙げられている「何個目の区間まで見たか」「センサー \(1\) を何個使ったか」「センサー \(2\) を何個使ったか」 のうち、この解法では後者 \(2\) つを使います。

DPの状態

\(\text{dp} [i][j] = (センサー1を i 個、センサー2をj個使ったときに、(最大何個目の区間の途中のまで監視できるか, その区間を何メートルまで監視できるか)の\text{pair})\)

ここでいうpairは、C++のstd::pair、Pythonのtupleを想像していただくとわかりやすいと思います。

pair \((i_1, j_1)\) と \((i_2, j_2)\)の大小比較は以下のようになります。

• \(i_1 \neq i_2\) のとき、 \(i_1\) と \(i_2\) の比較結果がpairの比較結果となる。

• \(i_1 = i_2\) のとき、 \(j_1\) と \(j_2\) の比較結果がpairの比較結果となる。

例としては、\(1\) 個目の区間の \(2\) メートルまで監視できるより、 \(2\) 個目の区間の \(1\) メートル まで監視できる方が、より進めているといえます。

DPの遷移

遷移は、今いる状態からセンサー \(1\) を \(1\) 個使用、センサー \(2\) を \(1\) 個使用の \(2\) つを考えればよいです。

初期化は、「\(1\) 番目の区間の \(0\) メートルの地点まで監視できる」です。

今、センサー \(1\) を \(i\) 個、センサー \(2\) を \(j\) 個使用して、 \(a\) 番目の区間の \(b\) メートルまで監視できるとします。 \(a\) が \(N+1\) であれば既にゴールしているとして、省略します。

そうでないとき、センサー \(1\) を次に使う場合、 \(b + L_1\) メートルまで監視できることになりますが、 \(b + L_1 \geq D_a\) のとき、 \(a\) 番目の区間はすべて監視ができるため、 「\(a+1\) 番目の区間の \(0\) メートルまで監視できる」とすることができます。

センサー \(2\) を使う場合も同様に考えることができます。

実装

あとは、DPの状態を見ていき、pairの1つ目の値が \(N+1\) であるようなもののうち、使用したセンサー \(1, 2\) の個数から価格の合計の最小値を求めることができます。

計算量は、入力に \(\Theta(N)\) 、DPに \(\Theta(K_1 K_2)\) かかるため、 \(\Theta(N + K_1 K_2)\) となります。

実装例 (C++) https://atcoder.jp/contests/abc325/submissions/46837144