2021-01-06から1日間の記事一覧
AtCoder
有志コン
DP高速化:セグメント木
セグメント木
しゃくとり法
DP高速化:しゃくとり法
区間
最適化テク:最適解の形を考える
in-place DP
DP
操作
操作の流れを単純化する
f(i,j)をiとjとに分離する
最適化テク:解を変形していく(最適性を失わずに)
操作:区間
操作:削除
最小コスト
ソートすることが目的の操作の問題
最適化問題
面白かった!セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね! 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…