豆を1回ずつ動かすのではなく、番号の大きいほうから小さいほうへと拾い集めながら動かしていく問題ととらえると、この問題は次のように言い換えることができます。

あなたは、 \(N-1\) マス目からスタートして、\(N - 1, N - 2 \dots, 1, 0\) と順番に移動していく。

あなたは 体力 と呼ばれるパラメータを持つ。体力の初期値は \(N-1\) であり、マスを移動するたびに \(1\) ずつ減っていく。

また、マスにいるときに行える 操作 がある。マス \(i\) で操作を行うと、あなたの体力は \(C_i\) へ変化する。\(A_i = 1\) である番号のマスでは必ず操作を行う必要があり、\(A_i = 0\) であるマスにおいては操作を行うかどうかは任意である。

移動の過程において体力が \(0\) 未満とならないように行動したときの操作回数の最小値を求めよ。

言い換え後の問題は、 \(\mathrm{dp[i][j]} =\) (現在マス \(i\) にいて体力が \(j\) であるときの操作回数の最小値) という DPを行うことによって、時間計算量および空間計算量 \(O(N^2)\) で解くことができます。