考虑转化为求最多说真话的人数
设$f(i)$表示排名前$i$的人中最多说真话的人的数量，考虑转移，如果由$j$转移而来，可以设$[j,i]$之间的人全都分数相等，那么式子就是$f[i]=f[j-1]+sum([j,i])$，其中$sum([j,i])$表示处在这个区间的人数，全部分数相等，另外如果人数多于区间数，多出来的人都在说谎
1 //minamoto 2 #include<bits/stdc++.h> 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<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 8 inline int read(){ 9 #define num ch-‘0‘ 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch==‘-‘)&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 const int N=100005; 19 vector<int> a[N];int n,f[N];map<pair<int,int>,int> x; 20 vector<int>::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 }
原文：https://www.cnblogs.com/bztMinamoto/p/9751798.html