ABC145 F - Laminate (600)
コンテスト中の考察
$ dp[i番目までで][j回変更して][高さv] になった時のコストの最小値を考える
$ O(N^3)で行けると思ったが、直前の高さは変化するので、$ O(N^4)の計算量になりTLE
解説を見た後
高さを変える場合は前と同じ高さにする場合だけ考えれば良い
これはその列が消えるのと同じ
前と同じ高さなら新たなコストは発生せず、後ろのコストが増えることも無い
最初の要素は前の要素が0であると考える必要がある
$ dp[i番目が最後で][全部でj列ある] 場合のコストの最小値を考える
それぞれで自分より前のiで全てのjの遷移を見るので$ O(N^3)
最後に全ての$ dp[i][N-K] の最小値を見れば良い
N-K未満だと消しすぎているので不適
$ dp[i] の要素は単調増加になるのでN-K以降を見る必要は無い
$ N \le Kの場合、全ての列を消した場合も考慮が必要