はまやんはまやんはまやん

hamayanhamayan's blog

イルミネーション (Illumination) [第18回日本情報オリンピック 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0656?year=2019

前提知識

解説

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/2/0656/judge/3760168/C++14

区間についての制約があって、合計の最大値」というのは、DPで解いたことがあるという経験がある。
なので、DPで解くというのも雑な解説なのだが、実際そうである。
制約を見てもDPっぽさがある。
DP[i] := 最後にi番目にイルミネーションを置いたときの美しさの合計の最大値

順番に置いていくことを考える。
i番目にイルミネーションを置くことを考えるとき、いくつもの制約をまとめて、[Ui, i)の範囲にはイルミネーションはおけないとなっているとする。
このとき、i番目にイルミネーションを置くと、美しさはA[i] + dp[Ui-1]となる。
これを考えると、Uiが構築できていればいい。

U[i]は[L[j],R[j]]の範囲にiが入っている中の、L[j]の最小値
となるので、これはいろいろなやり方があると思うが、自分は遅延セグメントツリーでゴリ押した。

int N, M, A[201010], L[201010], R[201010];
LazySegTreeMin<int, 1 << 18> U;
ll dp[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> L[i] >> R[i];

    rep(i, 0, M) U.update(L[i], R[i] + 1, L[i]);

    rep(i, 1, N + 1) {
        int u = U.get(i, i + 1);

        if (u == inf) chmax(dp[i], dp[i - 1] + A[i - 1]);
        else chmax(dp[i], dp[u - 1] + A[i - 1]);

        chmax(dp[i], dp[i - 1]);
    }

    cout << dp[N] << endl;
}