yukicoder - No.1077 Noelちゃんと星々4

問題リンク

解説

広義単調増加な数をつくればいいので、欲しいのは直前の情報だけでいいので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)) からのみ来ると考えても何も問題ありません。

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

提出コード

yukicoder.me