まずは条件を整理します。直感的には白マスが「階段状」に並ぶことですが、形式的に整理すると問題文中の条件は以下のように言い換えられます。

ある整数列 \((A_1, A_2, \ldots, A_N)\) が存在して、以下の条件をともに満たす（ただし、\(0 \leq A_i \leq N\) とする）。

• \(i\) 行目の左から \(A_i\) マスが白く塗られており、その他のマスは黒く塗られている。
• \(A_1 \geq A_2 \geq \ldots \geq A_N\) である。

\(1\) つ目の条件は問題文中の条件と同じですが、\(2\) つ目の条件は列に関する条件を \(A_i\) の大小関係に言い換えています。

このように整理すると、\(1\) 行ごとにマスの色を決める動的計画法により計算が行えます。\(dp_{i, j}\) を \(i\) 行目までの色を確定させ、\(A_i = j\) であるときの操作回数の最小値とします。

\(dp_{i - 1, *} \)の値から \(dp_{i, *}\) の値を求める計算順で答えを求めます。\(i\) 行目の左から \(j\) マスを白く、残りのマスを黒く塗るために必要な操作回数を \(D_{i, j}\) とすると、\(dp_{i, j} = D_{i, j} + \displaystyle\min_{j \leq k \leq N} dp_{i - 1, k}\) です。

上の式に従って愚直に dp の計算を行うと \(\Theta(N^3)\) 時間になってしまいますが、累積和を取るか \(D_{i, j}\) から \(D_{i, j + 1}\)（あるいは \(D_{i, j - 1}\)） が \(O(1)\) 時間で求められることを利用することで \(D_{i, j}\) の列挙は高速にでき、後ろから累積 min を取ることで \(\displaystyle\min_{j \leq k \leq N} dp_{i - 1, k}\) は高速に列挙できます。したがって、全体で \(O(N^2)\) 時間での計算が可能です。