問題
点が $N$ 個あたえられます．点 $i$ の高さは $Y_i$ です．Noel ちゃんは点の高さを自由に動かせます．ある日Noelちゃんは，点の高さが広義単調増加になるように点を動かしたくなりました．Noel ちゃんが動かす必要のある距離の総和の最小値を求めてください．ただし Noel ちゃんは，どの点も整数の距離だけしか高さを変えられないものとします．
要するに，与えられた数列を広義単調増加にしてください，という問題．
制約
- $1 \leqq N \leqq 10^{3}$
- $0 \leqq Y_i \leqq 10^{4}$
解法
dpで解く．配列は，$(N + 1) \times (\max\{Y\} + 1)$ の二次元配列として持つ．また，dp 配列の第 $(i, j)$ 要素は次のように定義される．
dp[i][j]：数列 $Y_0,Y_1,\dots,Y_{i-1}$ が広義単調増加となるように点の移動が完了しているとき，$Y_i$ を $j$ にしたときに必要なコストの最小値
※ ある数列 $\{A_i\}$ が広義単調増加であるとき，第 $i$ 番目の要素を $x$ としたとき，それ以前の要素（$A_0, A_1, \dots, A_{i-1}$）はすべて $x$ 以下である．
したがって，遷移の仕方は次のように表せる．
$$ \mathrm{dp}[i][j] = \min_{0 \leqq k \leqq j} \{ \mathrm{dp}[i-1][k] \} + | Y_i - j | $$
添字に注意して実装してあげると，以下のようになる．
n = int(input()) Y = list(map(int, input().split())) # 0-index mx = max(Y) INF = 10 ** 18 dp = [[INF] * (mx + 1) for _ in range(n)] # i = 0 のときを埋める for j in range(mx + 1): dp[0][j] = abs(Y[0] - j) # i >= 1 の場合を埋める for i in range(1, n): mn = 10 ** 18 for j in range(mx + 1): mn = min(mn, dp[i - 1][j]) dp[i][j] = mn + abs(Y[i] - j) print(min(dp[-1]))
例
入力
6 1 2 0 8 6 9
結果（実行後のdp配列）
for v in dp: print(v) # 以下ターミナル上での出力 [1, 0, 1, 2, 3, 4, 5, 6, 7, 8] [3, 1, 0, 1, 2, 3, 4, 5, 6, 7] [3, 2, 2, 3, 4, 5, 6, 7, 8, 9] [11, 9, 8, 7, 6, 5, 4, 3, 2, 3] [17, 14, 12, 10, 8, 6, 4, 4, 4, 5] [26, 22, 19, 16, 13, 10, 7, 6, 5, 4]
