Codeforces 1841D Pairs of Segments

题目来自 Codeforces Educational Round #150 (Div.2) D。link

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

给出 \(n\) 个闭区间 \([l_1,r_1], [l_2,r_2], ..., [l_n,r_n]\)。你需要去除其中的 \(k\) 个区间，满足：可以将剩下的区间分为 \(\frac{n-k}{2}\) 对，使得每一对区间有交集，且与其他对的区间没有交集。输出 \(k\) 的最小值。

\(1\leq t\leq 1000, 2\leq n\leq 2000, 0\leq l_i\leq r_i\leq 10^9\)。

Tutorial

首先注意到 "区间没有交集" 这一经典的区间 DP 性质，这为题目的解决提供了单调性。若我们将所有区间按照左端点排序，那么对于 \(i<j<k\)，如果区间 \(i\) 与区间 \(j\) 不相交，它与区间 \(k\) 也不相交。

根据这个事实我们有结论，对于选定的区间 \(i\)，若我们要选择相交的区间 \(j\) 与之配对，那么区间 \(j\) 的右端点越小越好；因为一旦 \(j\) 被确定，所有左端点 \(< j\) 右端点的区间都将被去除。

在左区间选定的情况下存在选择右区间的最佳策略，于是考虑倒序进行 DP：令 \(dp[i]\) 为第 \([i,n]\) 个区间中我们最多能够选取的区间的数量，那么最终的答案 \(k_{min}=n-dp[1]\)。考虑选取/不选取第 \(i\) 个区间进行转移：

• 不选取区间 \(i\)。此时 \(dp[i]=\max(dp[i], dp[i+1])\)。
• 选取区间 \(i\)。此时我们需要找到一个与区间 \(i\) 相交的，且右端点最小的区间 \(j\) 与之配对。找到区间 \(j\) 后，所有与区间 \(i\) 与区间 \(j\) 相交的区间将被去除。因此 \(dp[i]=dp[k]+2\)，\(k\) 为 \([j+1,n]\) 中最左边 (leftmost) 的，不与区间 \(i\) 与区间 \(j\) 相交的区间。

Solution from silxi

Code Implementation

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 2010;

struct segment {
    int l, r;
    bool operator < (const segment& x) const {
        return (l == x.l) ? r < x.r : l < x.l;
    }
} seg[MAX_N];

int dp[MAX_N];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)    cin >> seg[i].l >> seg[i].r;
        for (int i = 1; i <= n + 1; ++i)    dp[i] = 0;
        sort(seg + 1, seg + n + 1);
        for (int i = n; i >= 1; --i) {
            dp[i] = max(dp[i], dp[i + 1]);
            int j = 0, minr = 1e9;
            for (int p = i + 1; p <= n; ++p) {
                if (seg[p].l <= seg[i].r) {
                    if (seg[p].r <= minr) {
                        minr = seg[p].r;
                        j = p;
                    }
                } else {
                    break;
                }
            }
            if (!j) continue;
            int k = 0;
            for (int p = j + 1; p <= n; ++p) {
                if (seg[p].l > max(seg[i].r, seg[j].r)) {
                    k = p;
                    break;
                }
            }
            dp[i] = max(dp[i], dp[k] + 2);
        }
        cout << n - dp[1] << endl;
    }

    return 0;
}