F - Insertion Sort - マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）
セグ木で差分を更新する方法が勉強になった。
----------------------------------------------------
問題
長さNの順列Pが与えられる。
左からi番目の値はPiである。
以下の操作を使ってPiを昇順に並べたい。
・i(1<=1<=N)を選ぶ。コストAiでiを好きな場所に移動
・i(1<=1<=N)を選ぶ。コストBiでiを左端に移動
・i(1<=1<=N)を選ぶ。コストCiでiを右端に移動
合計コストを最小化してください。
-----------------------------------------------------
動かさない番号をS1....Skとすると
S1未満の番号は左端に動かすべきであり
Skより上の番号は右端に動かすべきであり
それ以外は任意の場所に動かす必要があると決まる。
よって以下のようにdpを決める。
dp[i] := i番目が動かさない最後の番号とした時に、i番目までを昇順に並べる最小コスト
ここで答えはmin(dp[i] + (A[i+1] + ... + A[N-1]));になる
またdpの遷移は以下のように書ける。
dp[i] = min(B[0]+...+B[i-1], dp[j] + A[j+1]+...+A[i-1]);
左は自分の左に動かさない番号が無い場合であり
右は直前の動かない番号がjである場合である。
この遷移をセグ木で高速化する。
厄介なのは選んだjによって足されるAの値が異なる事であり、セグ木から取り出した値に同じ値を足せば
dpの値になるように出来ればいいので
seg[i] := dp[i] - A[i]
としておけば
任意のjについてdp[i] = seg(0, i) + A[0]+...+A[i-1]
と扱えるためこの問題が解けた
図にすると下のようになる
答えの値について緑の長さを足してやる必要がある時に
あらかじめ赤線の部分を引いておくことで
どの値についても同じ緑の長さを足せばいいようにした。
