問題文と同様に、変更後の \(A_1, A_2, \ldots, A_N\) の値をそれぞれ \(B_1, B_2 \ldots, B_N\) で表します。

\(S := \sum_{k = 1}^{N} A_k\) とおくと、この問題は、 \(\sum_{k = 1}^N B_k = S\) かつ \(B_1 = B_N = 0\) を満たすという条件下で、 コスト \( \sum_{k = 1}^{N-1} f(B_k, B_{k+1})\) を最小化するような \(N\) 個の非負整数 \(B_1, B_2, \ldots, B_N\) の組み合わせを決定する問題です。 ここで、\(f(B_k, B_{k+1})\) は、 点 \(P_k(k, B_k)\) と点 \(P_{k+1}(k+1, B_{k+1})\) を結ぶ線分の長さ \(\sqrt{1+(B_k-B_{k+1})^2}\) です。

しかし、\(\sum_{k = 1}^N B_k = S\) かつ \(B_1 = B_N = 0\) を満たす \(N\) 個の非負整数 \(B_1, B_2 \ldots, B_N\) の組み合わせの個数は莫大であるため、これらを全探索する方法では、実行制限時間内に答えを求めることはできません。

したがって、動的計画法を用いてこの問題を解きます。 \(\mathrm{dp}[i][sum][last]\) を次のように定義します：

\(\mathrm{dp}[i][sum][last]\)は、\(\sum_{k=1}^i B_k = sum\) かつ \(B_i = last\) を満たすように \(B_1, B_2, \ldots, B_i\) を決定するときの、コスト \(\sum_{k = 1}^{i-1} f(B_k, B_{k+1})\) の最小値

このとき、この問題の答えは、 \(\mathrm{dp}[N][S][0]\) となります。（制約 \(B_N = 0\) より、\(last > 0\) における \(\mathrm{dp}[N][S][last]\) は問題の答えとはなり得ないことに注意してください。）

よって、\(\mathrm{dp}[N][S][0]\) の値を求めることを最終的な目標として、各 \(i = 1, 2, \ldots, N\)、\(sum = 0, 1, 2, \ldots, S\) および \(last = 0, 1, 2, \ldots, sum\) について、\(\mathrm{dp}[i][sum][last]\) の値を計算することを考えます。

• まず、\(\mathrm{dp}[1][0][0]= 0\) です。制約 \(B_1 = 0\) より、\(B_1 = 1, 2, \ldots, S\) となることはないので、 \(sum \neq 0\) かつ \(last \neq 0\) の場合には便宜上 \(\mathrm{dp}[1][sum][last] = \infty\) とします。
• \(i = 2, 3, \ldots, N\)については、
  \(\mathrm{dp}[i][sum][last] = \displaystyle\min_{0 \leq j \leq S}\mathrm{dp}[i-1][sum-last][j] + f(j, last)\) \(\cdots (\ast)\)
  が成り立ちます。
  何故ならば、\(B_1, B_2, \ldots, B_i\) が \(\sum_{k=1}^i B_k = sum\) かつ \(B_i = last\) を満たすという条件下でコスト \(\sum_{k= 1}^{i-1} f(B_k, B_{k+1})\) を最小にするとき、 \(B_1, B_2, \ldots, B_{i-1}\) は　\(\sum_{k=1}^{i-1} B_k = sum - last\) を満たすという条件下でコスト \(\sum_{k = 1}^{i-2} f(B_k, B_{k+1})\) を最小にします。 よって、このときの \(B_{i-1}\) を \(j_0\) とおくと、 \(\mathrm{dp}[i][sum][last] = \mathrm{dp}[i-1][sum-last][j_0] + f(j_0, last)\) が成り立ちます。 \(j_0\) は \(0, 1, 2, \ldots, S\) のいずれかですので、上記の式 \((\ast)\) が成り立ちます。

上記の漸化式を用いて、各 \(\mathrm{dp}[i][sum][last]\) の値を順番に計算すれば、 先ほど述べた通り \(\mathrm{dp}[N][S][0]\) がこの問題の答えとなるので、この値を出力すれば良いです。

このアルゴリズムの時間計算量は \(\mathrm{O}(NS^3)\) であり、この問題を正解するためには十分高速です。