AtCoder Regular Contest 070 E - NarrowRectangles

考察してて生えてきた図に既視感があると思ったら、以前諦めて解説だけ見た問題だった

$dp[i][x]=i個目の左端をxとしたときのi個目までの総移動量の最小値$

というDPについて考えます。以下が成り立ちます。

$dp[i][x]=\displaystyle \min_{x-(r_{i-1}-l_{i-1}) \leq x' \leq x+(r_i-l_i)} dp[i-1][x'] + |x-l_i|$

ここまでで部分点が取れます。
実は $dp[i]$ は、傾きが段階的に変化するU字状の関数になっており、傾きが変わる点の集合をとして管理することができます。具体的には、

傾き $0$ のところから点を左右に分け、左側を降順、右側を昇順のpriority_queueとして持つ。左右それぞれで点同士の相対位置が正しくなるようにする。傾き $0$ の線の両端の点だけ正しい座標を持っておく。
漸化式の第1項を処理することを考える。傾き $0$ の線が広がることがわかるので、両端の点の座標を更新する。
漸化式の第2項を処理することを考える。ある点で傾きが $2$ 変わることがわかるので、priority_queueに同じ点を2つ追加し、左右間で点を受け渡す。座標と答えを更新する。