https://ngtkana.hatenablog.com/entry/2020/05/30/014836

問題

atcoder.jp

解説

行きと帰り（復元）があります。

行き

まずは、コストが最小となるような、最後においたブロックの左端の X 座標の範囲を DP です。これはダブルヒープでシュミレーションができます。（※ この解説はダブルヒープで凸折れ線を扱うテクになれていることを仮定します。（はい？））

帰り

すると、最後のブロックを置くべき場所の範囲が決まりますから、適当に左端にでもおいておきましょう。すると、各ブロックについて

後ろのすでに場所を決めたブロックとの兼ねあいで、おいて良い場所

が順番に決まり、また、

前のこれから場所を決めるブロックを最適化したときにコストが最小になる区間

はすでにわかっていますから、この情報から、置くべき場所が決まります。

実装の方針

コスト関数の遷移は 2 つに分かれます。各区間の左端を $x_i$ , 長さを $l_i$ と書きましょう。1つ目の遷移はこれです。

$f(x) ←f.min (x - l_i, x - l_{i_1} )$

2 つ目の遷移は

$f(x) += |x - x_i|$

です。

2 つ目はダブルヒープの基本で、左右のヒープに入れてスワップをすると良いです。問題は 1 つ目なのですが、これは左のヒープの中身をすべて $-l_i$ して、右をすべて $+l_{i-1}$ することに等しいです。もちろんこれを愚直に実装すると遅いですから、遅延評価です。

実装の詳細

入力です。

usize n;
std::cin >> n;
vec<i64> x(n), len(n);
for (usize i=0; i<n; i++) {
    std::cin >> x.at(i) >> len.at(i);
    len.at(i) -= x.at(i);
}

行きの準備です。まず凸関数とはいっても定数関数は扱いづらいですから、はじめの 1 つのブロックは処理してしまいましょう。これは元あった場所が最適です。左右のヒープに入れておきましょう。また、遅延評価用の変数、gl, gr を用意です。また、復元用に最小の範囲を ml, mr にメモです。

std::priority_queue<i64, vec<i64>, std::less<>> pl;
std::priority_queue<i64, vec<i64>, std::greater<>> pr;
vec<i64> ml(n), mr(n);
i64 gl=0, gr=0;
ml.at(0) = x.at(0);
mr.at(0) = x.at(0);
pl.push(x.at(0));
pr.push(x.at(0));

行きです。下駄に注意しながらダブルヒープをします。

for (usize i=1; i<n; i++) {
    assert(pl.top()-gl <= pr.top()+gr);
    gl += len.at(i);
    gr += len.at(i-1);
    pl.push(x.at(i) + gl);
    pr.push(x.at(i) - gr);
    pl.push(pr.top()+gr+gl); pr.pop();
    pr.push(pl.top()-gr-gl); pl.pop();
    ml.at(i) = pl.top()-gl;
    mr.at(i) = pr.top()+gr;
}

帰りです。下駄のことはもう忘れて良しです。選べる中から最小になるように選んでいきましょう。

vec<i64> pos(n);
pos.at(n-1) = ml.at(n-1);
for (usize i=n-2; i!=-1; i--) {
    i64 l = pos.at(i+1) - len.at(i);
    i64 r = pos.at(i+1) + len.at(i+1);
    pos.at(i) = r < ml.at(i)
        ? r
        : mr.at(i) < l
        ? l
        : ml.at(i)
        ;
}

出力です。

i64 ans = 0;
for (usize i=0; i<n; i++) {
    ans += std::abs(pos.at(i) - x.at(i));
}
std::cout << ans << '\n';