解説

広義単調増加な数をつくればいいので、欲しいのは直前の情報だけでいいのでdpをしたくなります。

ここで作る数列は $[0, 10000]$ としていいです。こうなると簡単にdpが定義できて、

$dp[i][j] := i番目までみたとき、i番目がjにしたときの最小のコスト$

となるでしょう。

後は遷移ですが、広義単調増加でないといけないので、 $dp[i][j]$ の遷移は $dp[i - 1][k] \ (1 \leq k \leq j)$ のみから来ます。

よって、 $dp[i][j]$ の遷移は $min (dp[i - 1][k] \ (1 \leq k \leq j))$ からのみ来ると考えても何も問題ありません。

あとは最小値を取りながら更新していけば解くことができました！！

提出コード