\(A\) の各要素が、隣接する要素と同時に \(0\) になるか、単独で \(0\) になるかを考えると、\(A\) は長さが \(1\) または \(2\) のいくつかの区間に分割できます。このときのコストの和は、各区間の最大値の和であり、これを最小化する分割を考える問題を考えます。

全ての区間が長さ \(1\) になるように分割する場合は、操作によって達成できませんが、それは明らかにコスト和が最適でないため考えなくて良いです。逆に、長さが \(2\) の区間が存在すれば対応する操作が存在します。よって、\(A\) を長さが \(1\) または \(2\) のいくつかの区間に分割し、各区間の最大値の和を最小化する問題を解けばそのまま答えになります。

以下のような \(\text{dp}\) の定義をすることで、 \(O(N)\) で解くことができます。

\(\text{dp}[i]\coloneqq\) (\(A_1,\dots ,A_i\) を全て \(0\) にするために必要なコスト和の最小値)

\(\text{dp}[i] = \min(\text{dp}[i-1] + A_i, \ \text{dp}[i-2] + \max(A_{i-1},A_i))\)