問題概要

$N$ マスがあって、最初はすべて白色である。以下の $M$ 種類の操作を好きな順序で好きな回数行うことができる。

$i$ 種類目の操作: マス $L_{i}$ からマス $R_{i}$ までを黒色で塗る

マス目の状態を変化させるような操作の回数の最大値を求めよ。

制約

$1 \le N \le 500$
$0 \le M \le \frac{N(N+1)}{2}$

考えたこと

コンテスト中は嘘貪欲を考えていた。「長さ 1 の操作があればそれは必ず使って良くて、その操作の占めていた区間を縮約して、残りの問題を考えれば良い」までは正しい。

しかし、「長さ 1 の操作がない場合でも、長さが最小の操作を必ず使って良いと考えていいのではないか」と予想して、これが嘘だった。たとえばサンプル 4 に対して、正しくない。

そこで正攻法を考える。黒色マスが増えていく様子は、入れ子構造のようになっている。こういう構造を紐解く時は、確かに区間 DP が有効なのであった。

区間 DP

区間 $\lbrack l, r)$ 内部について、操作列の最大値を求めたい。次のように考えることにした。

最後の操作によって黒色に変わるマス $v$ の位置で場合分けする

マス $v$ を含む操作であって、区間 $\lbrack l, r)$ 内部におさまるものが存在すれば、それを最後の操作として、

区間 $\lbrack l, v)$ についての小問題
区間 $\lbrack v+1, r)$ についての小問題

へと分解できる。まさに区間 DP そのもの。もし、「マス $v$ を含む操作であって、区間 $\lbrack l, r)$ 内部におさまるものが存在するか」どうかの判定を $O(1)$ でできるならば、区間 DP の処理に要する計算量は $O(N^{3})$ となる。

その存在判定を高速でできるようにするために、次の配列を前処理で求めておくこととした。これは $O(NM)$ の計算量で容易に求められる。

minR[v][l] := 区間 $\lbrack v, v+1)$ を含む操作のうち、左端が $l$ 以上であるものの中での右端の最小値 (存在しない場合は $N+1$ )

全体として、計算量は $O(NM + N^{3})$ となった。

コード

#include <bits/stdc++.h>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> left(M), right(M);
    for (int i = 0; i < M; ++i) {
        cin >> left[i] >> right[i];
        --left[i];
    }
    
    // minR[v][l] := 区間 [v, v+1) を含む操作であって、左端が l 以上であるものの中での右端の最小値 (存在しない場合は N+1)
    vector<vector<int>> minR(N+1, vector<int>(N+1, N+1));
    for (int v = 0; v < N; ++v) {
        for (int id = 0; id < M; ++id) {
            if (right[id] <= v || v+1 <= left[id]) continue;
            for (int l = 0; l <= left[id]; ++l) {
                chmin(minR[v][l], right[id]);
            }
        }
    }
    
    // 区間 DP
    vector<vector<int>> dp(N+1, vector<int>(N+1, -1));
    auto rec = [&](auto self, int l, int r) -> int {
        if (dp[l][r] != -1) return dp[l][r];
        if (l >= r) return 0;
        
        int res = 0;
        
        // 最後に置くマスで場合分け
        for (int v = l; v < r; ++v) {
            // 区間 [v, v+1) を含み、全体が [l, r) におさまるような操作が存在しない場合はスキップ
            if (minR[v][l] > r) continue;
            
            chmax(res, 1 + self(self, l, v) + self(self, v + 1, r));
        }
        return dp[l][r] = res;
    };
    int res = rec(rec, 0, N);
    cout << res << endl;
}