解法

这道 DP 出的很好，考察了选手模型转换的能力。

第\(i\)个人说：“有\(ai\)个人分数比我高，\(bi\)个人分数比我低。”

每一句话都可以看作是一维坐标上的一条线段\([a_i+1,n-b_i]\)，表示这一段线段上的人成绩相等。显然，对一每一种合法情况，这些线段都不会相交（允许完全重合）。所以将线段按左端点排序，这个以坐标位关键字的\(dp\)方程应该写成：

\[ dp[i] = dp[i-l] + min(\text{线段长度}, \text{线段个数}) \]

代码

// BZ2298.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 101000;
int n, dp[MAX_N], cnt;
struct pr
{
    int first, second;
    bool operator<(const pr &p) const
    {
        return second < p.second || (second == p.second && first < p.first);
    }
} res[MAX_N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x + y < n)
            res[++cnt].first = x + 1, res[cnt].second = n - y;
    }
    sort(res + 1, res + 1 + cnt);
    int cur = 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1];
        int tmp = 0;
        while (res[cur].second < i)
            cur++;
        for (; res[cur].second == i; cur++)
        {
            if (res[cur].first == res[cur - 1].first)
                tmp++;
            else
                tmp = 1;
            dp[i] = max(dp[i], dp[res[cur].first - 1] + min(tmp, i - res[cur].first + 1));
        }
    }
    printf("%d", n - dp[n]);
    return 0;
}