[haoi2011]a

一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

题解：首先，由每个人说的话的内容，我们可以理解为他处在ai+1,n-bi这个区间（分数段）内，且这个区间每个人的分数相等；

有n个这样的区间，可以看出，交叉的区间不能一起选，完全相同的区间可以一起选；

这样我们把相同的区间数目求出来作为这个区间的权值，这个问题就成了带权的选择权值之和最大的不相交的区间问题；

利用动态规划解决即可；

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define FILE "a"
#define LL long long 
#define up(i,j,n) for(int i=j;i<=n;i++)
#define pii pair<int,int>
#define piii pair<int,pii >
template<typename T> inline bool chkmin(T &a,T b){return a>b?a=b,true:false;}
template<typename T> inline bool chkmax(T &a,T b){return a<b?a=b,true:false;}
namespace IO{
    char *fs,*ft,buf[1<<15];
    inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
    inline int read(){
        LL x=0;int ch=gc();bool f=0;
        while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
        while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
        return f?-x:x;
    }
}using namespace IO;
namespace OI{
    const int maxn(101000);
    struct node{
        int x,y;
        bool operator<(const node &b)const{return x<b.x||(x==b.x&&y<b.y);}
        bool operator==(const node &b){return x==b.x&&y==b.y;}
    }a[maxn];
    int n,f[maxn];
    struct Node{
        int y,v,next;
    }e[maxn];
    int linkk[maxn],len=0;
    void insert(int x,int y,int v){
        e[++len].y=y;
        e[len].next=linkk[x];
        linkk[x]=len;
        e[len].v=v;
    }
    void slove(){
        n=read();
        up(i,1,n)a[i].x=read()+1,a[i].y=n-read();
        sort(a+1,a+n+1);
        up(i,1,n){
            int j=i,v;
            while(a[j+1]==a[i])j++;
            v=j-i+1;
            if(a[i].y-a[i].x+1<v)v=a[i].y-a[i].x+1;
            insert(a[i].x,a[i].y,v);
            i=j;
        }
        up(i,1,n){
            chkmax(f[i],f[i-1]);
            for(int j=linkk[i];j;j=e[j].next)chkmax(f[e[j].y],f[i-1]+e[j].v);
        }
        printf("%d
",n-f[n]);
    }
}
int main(){
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    using namespace OI;
    slove();
    return 0;
}