牛客动态规划课程习题-PROBLEM A

题意：n个人，每个人都说剩下人中比自己分数高的人有ai个，比自己分数低的有bi个，问最少有多少人说谎。题中允许同分人出现。
题解：我们可以这么考虑，在所有人中，当前人的排名是[ai+1,n-bi]。在一个合法的情况下，任意两个人的区间是不能相交的。对于一对(i,j),可能会出现ai=aj,bi=bj.所以每个区间相当于有一个权值，代表这个选择这个区间的能带来多少人没有说谎。最后题目就转化成1-n的区间内，选择一些不相交区间使得区间权值和最大。（注意考虑区间的权值不能大于区间长度）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,l,r,tot;
map<pair<int,int>, int >mp;
struct node{
  int l,r;
  bool operator<(const node a)const{
    if (r!=a.r)return r<a.r;
    else return l<a.l;
  }
}p[maxn];
int dp[maxn];
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&l,&r);
        if (l+r>=n)continue;
        int a=l+1,b=n-r;
        mp[make_pair(a,b)]++;
        if (mp[make_pair(a,b)]==1)p[++tot]={a,b};
    }
    sort(p+1,p+tot+1);
    int nowp=1;
    for (int i=1;i<=n;i++){
      dp[i]=dp[i-1];
      while (nowp<=tot&&i>=p[nowp].r){
        dp[i]=max(dp[i],dp[p[nowp].l-1]+min(p[nowp].r-p[nowp].l+1,mp[make_pair(p[nowp].l,p[nowp].r)]));
        nowp++;
      }
    }
    cout<<n-dp[n]<<endl;
    return 0;
}