JOI 予選 2019 E - イルミネーション (AOJ 0656, 難易度 7)

区間についてどうのこうのする問題、大抵は DP！

問題へのリンク

問題概要

個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間

• [ ]

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

制約

• 
• 

考えたこと

とりあえず、区間をどうのこうのする問題は

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

のどちらにしようか悩むのだけど、今回に関してはある区間を選んだとして、その中のどの点を選ぶかで結局各マスに関する考察が必要になってしまう。ので、マスを左から順に処理する 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 ]

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

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