\(N\) 個のマスの高さをそれぞれ \(X_1,X_2,\dots,X_N\) とするために必要な魔法をかける回数としてありうる最小値について考えます。

\(X_0=0,X_{N+1}=0\) とおき、 \(Y_i=X_{i}-X_{i-1} (1\le i\le N+1)\) とします。すると、はじめすべて \(0\) である \(N\) 個の整数 \(y_1,y_2,\dots,y_{N+1}\) に次の操作を行って各 \(i(1\le i\le N+1)\) について \(y_i=Y_i\) にするときの操作の最小回数と言い換えられます。

• \(1\le i< j\le N+1\) なる整数の組 \((i,j)\) であって \(y_{i+1}=\dots=y_{j-1}=0\) であるものを選び \(y_i\) に \(1\) を足し \(y_j\) から \(1\) を引く。

外側から順に操作を行えばよいため \(y_{i+1}=\dots=y_{j-1}=0\) という条件は無視できます。

操作回数を最小化したものについて各 \(y_i\) は加算されるのみか減算されるのみかのどちらかです。

よって、 \(Y_i(1\le i\le N+1)\) のうち正のものの総和は加算される回数の最小値、すなわち魔法をかける回数の最小値と等しいので \(\sum_{1\le i\le N+1} \max(X_{i}-X_{i-1},0)\) とわかります。

すると次のような dp を立てることができます。

\(\mathrm{dp}[i][j]:=\) \(X_i\) まで決め \(X_i=j\) であるときの \(\sum_{1\le k\le i} \max(X_{k}-X_{k-1},0)\) の最小値

初期化は \(\mathrm{dp}[0][0]=0\) 、遷移は \(\mathrm{dp}[i][j]=\min(\mathrm{dp}[i],\min_{k=0,1,\dots,j-D[i-1]}(\mathrm{dp}[i-1][k]+(j-k)),\min_{k=j+D[i-1],\dots,j_{\max}}(\mathrm{dp}[i-1][k]+(k-j)))\) で、\(j_{\max}=D_1+\dots,D_N\le ND_{\max}\) なので、累積 min をとると \(\Theta(N^2D_{\max})\) 時間で計算できます。