https://kanpurin.hatenablog.com/entry/2021/05/27/064905

問題はこちら

問題概要

${N}$ がいて，左から ${i}$ 番目は人 ${P_i}$ である．以下の ${3}$ 種類の操作を繰り返し，人を昇順に並び替えるときのコストの最小値を求めよ．

コスト ${A_i}$ を払い，人 ${i}$ を好きな位置に移動させる．
コスト ${B_i}$ を払い，人 ${i}$ を左端に移動させる．
コスト ${C_i}$ を払い，人 ${i}$ を右端に移動させる．

${1\leq N\leq 2×10^5\\ 1\leq P_i\leq N\\ 1\leq A_i,B_i,C_i\leq 10^9}$

解説

${B_i\leftarrow \min(A_i,B_i),C_i\leftarrow \min(A_i,C_i)}$ とする．
それぞれの操作は元の位置によらないので，各人に対しての操作は高々 ${1}$ 回でいい．

操作をしない人を決める(ただし番号は昇順)ことにより，他の人に対する操作が決まる．例として以下の問題を考える．

f:id:kanpurin:20210527012714p:plain:w400

人 ${2}$ ，人 ${4}$ ，人 ${5}$ を操作しないと決める(選ばれなかった人は必ず動かす)

f:id:kanpurin:20210527015240p:plain:w400

人 ${1}$ は左端に移動する操作，人 ${3}$ は好きな位置に移動する操作，人 ${6}$ は右端に移動する操作を行う．より一般的には，操作をしないと決めたすべての人よりも数が小さい人は左端に移動し，操作をしないと決めたすべての人よりも数が大きい人は右端に移動し，その他の人は好きな位置に移動する操作を行う必要がある．

番号の昇順に操作をしない人を選ぶように考えることで以下のようなDPで解ける．
${dp[i]を}$ 「 ${i}$ 番目まで決めて最後に人 ${i}$ を選んだときの最小コスト」とする．元の順番で人 ${i}$ より左側にいるような人 ${j(j < i)}$ について，人 ${j}$ を選び， ${j < x < i}$ となる人 ${x}$ は選ばないとすると $dp[j]+\sum_{k=j+1}^{i-1}A_k$ の最小値が ${dp[i]}$ となる．ただし，人 ${i}$ を最初に選ぶときは ${\displaystyle\sum_{k=0}^{i-1}B_k}$ となる．
まとめると， $dp[i]=\min\left(\underset{j\in S}{\min}\left(dp[j]+\sum_{k=j+1}^{i-1}A_k\right),\sum_{k=0}^{i-1}B_k\right)$ ．ただし， ${S}$ は ${j < i}$ かつ元の順番で人 ${j}$ が人 ${i}$ より左にいるような ${j}$ の集合とする．

${\begin{eqnarray} \displaystyle dp[i] &=& \min\left(\underset{j\in S}{\min}\left(dp[j]+\sum_{k=j+1}^{i-1}A_k\right),\sum_{k=0}^{i-1}B_k\right)\\ \displaystyle &=& \min\left(\underset{j\in S}{\min}\left(dp[j]-\sum_{k=1}^{j}A_k\right)+\sum_{k=1}^{i-1}A_k,\sum_{k=0}^{i-1}B_k\right) \end{eqnarray}}$

${\displaystyle\underset{j\in S}{\min}\left(dp[j]-\sum_{k=1}^{j}A_k\right)}$ が高速に求められれば解ける．

${i}$ の昇順に ${\displaystyle\underset{j < i\land p(j) < p(i)}{\min}f(j)}$ みたいなものを求めるのは典型で， ${i}$ の昇順にSegmentTreeの ${p(i)}$ の位置に ${f(i)}$ を入れていけば区間最小値を求める問題になって高速に解ける．