考虑转化为求最多说真话的人数

设$f(i)$表示排名前$i$的人中最多说真话的人的数量，考虑转移，如果由$j$转移而来，可以设$[j,i]$之间的人全都分数相等，那么式子就是$f[i]=f[j-1]+sum([j,i])$，其中$sum([j,i])$表示处在这个区间的人数，全部分数相等，另外如果人数多于区间数，多出来的人都在说谎

1 //minamoto 2 #include
     
       3 #define mp(i,j) make_pair(i,j) 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template
      
       inline bool cmax(T&a,const T&b){
   return a
       

a[N];int n,f[N];map

,int> x;20 vector

::iterator ii;21 int main(){22 // freopen("testdata.in","r",stdin);23 n=read();24 for(int i=1;i<=n;++i){25 int l=read(),r=read();26 ++l,r=n-r;27 if(l>r) continue;28 if(++x[mp(l,r)]==1) a[r].push_back(l);29 }30 for(int i=1;i<=n;++i){31 f[i]=f[i-1];32 for(ii=a[i].begin();ii!=a[i].end();++ii)33 cmax(f[i],f[(*ii)-1]+min(i-(*ii)+1,x[mp(*ii,i)]));34 }35 printf("%d\n",n-f[n]);36 return 0;37 }