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; }