けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 0656 イルミネーション (JOI 2019 予選 E)

区間に対してどうこうする DP 苦手意識ある。。。
区間スケジューリング問題に近い感じ。

問題へのリンク

問題概要

 N 個の整数  A_1, A_2, \dots, A_N がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 M区間

  • [  L_i, R_i ]

があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。

制約

  •  1 \le N \le 2 × 10^{5}
  •  1 \le M \le 2 × 10^{5}

考えたこと

典型なのはわかるのだけど僕の安心できる実家じゃない。。。
とりあえず、区間をどうのこうのする問題は

  • 区間を左から順に処理していく (適切に区間の始点や終点でソートしておく)
  • マスを左から順に処理していく

のどちらにしようか悩むのだけど、今回に関してはある区間を選んだとして、その中のどの点を選ぶかで結局各マスに関する考察が必要になってしまう。ので、マスを左から順に処理する DP にしてみる。シンプルに

  • dp[ i ] := マス i-1 を選びつつ、[0, i) から選ぶ最大値

として集める DP で漸化式を組んでみる。

  • prev[ i ] := マス i-1 と x-1 とが同一区間上にならないような x (< i) の最大値

を前処理として求めておいて

dp[ i ] = max_{j <= prev[ i ]} (dp[ j ]) + A[ i-1 ]

となる。この後半部分はセグメントツリーを使ってもいいが、普通に累積 max で高速化できる。

  • maxdp[ i ] = max_{j <= i} (dp[ j ])

とすれば

dp[ i ] = maxdp[ prev[ i ] ] + A[ i ]

となる。地味に定番の区間ソートがなくて、計算量は  O(N + M) でできる。

#include <iostream>
#include <vector>
using namespace std;
using pint = pair<int, int>;
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } else return false; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } else return false; }

int main() {
    int N, M; cin >> N >> M;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    vector<pint> ins(M);
    for (int i = 0; i < M; ++i) cin >> ins[i].first >> ins[i].second, --ins[i].first;
    
    // prev[i] = マス i-1 と x-1 とが同一区間上になりような x の最大値
    vector<int> prev(N + 1, N + 1);
    prev[N] = N-1;
    for (int i = 0; i < M; ++i) chmin(prev[ins[i].second], ins[i].first);
    for (int i = N - 1; i >= 0; --i) chmin(prev[i], min(prev[i + 1], i - 1));
    
    // 累積 max を用いた DP
    vector<long long> dp(N + 1, 0), maxdp(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        chmax(dp[i], maxdp[prev[i]] + A[i - 1]);
        chmax(maxdp[i], max(maxdp[i - 1], dp[i]));
    }
    cout << maxdp[N] << endl;
}