背包

转化为 求最大不重合区间权值和的问题 就非常直观了。

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define x first
#define y second
map<int, int> mp[N];
int n, a, b;
int dp[N];  //最大
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a, &b);  // a个人比他高 b个人比他低
        if (a + b > n) continue;
        mp[b][n - a]++;  // n-a ：不高于他的人数 也就是说，n-a=b+同分人数
    }
    for (int i = 0; i < n; i++) {
        for (auto it : mp[i])
            dp[it.x] = max(dp[it.x],              //可以放弃这个区间
                           dp[i] + min(it.x - i,  //同分的容纳上限n-a-b
                                       it.y));    //有多少个报了这个的
        dp[i + 1] = max(dp[i + 1], dp[i]);        //可以放弃这个区间
    }
    printf("%d\n", n - dp[n]);
    return 0;
}