https://www.lydsy.com/JudgeOnline/problem.php?id=2298
https://www.luogu.org/problemnew/show/P2519
好题啊，以及我的dp为什么这么烂……算了吐槽放后面。
参考洛谷题解。
显然a+b+1>n一定是谎话，直接特判。
然后考虑冲突，显然两人名次相同的情况下a和b不同就说明这两人只能取1个/种（因为名次相同且a和b相同则可能有相同分数。）
为了更好表示，我们另[l,r]表示按照成绩排序后这个人位于这些人的[l,r]区间内，对这个区间赋予说真话人数的价值。
则当同一类人超过r-l+1个时显然只有r-l+1人说了真话。
以及重叠的多个区间间只能取一个。
我们dp做即可，具体可以看代码。（吐槽放代码后面了。）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct people{
int l,r;
}p[N];
struct line{
int l,r,v;
}q[N];
int f[N],nxt[N],cnt,tot=,num,n;
inline bool cmp1(people a,people b){
return a.l<b.l||(a.l==b.l&&a.r<b.r);
}
inline bool cmp2(line a,line b){
return a.r<b.r||(a.r==b.r&&a.l<b.l);
}
int main(){
n=read();
for(int i=;i<=n;i++){
int a=read(),b=read();
if(a+b+>n)continue;
p[++cnt].l=a+;p[cnt].r=n-b;
}
sort(p+,p+cnt+,cmp1);
for(int i=;i<=cnt+;i++){
if(p[i].l==p[i-].l&&p[i].r==p[i-].r)tot++;
else{
q[++num].l=p[i-].l;q[num].r=p[i-].r;
q[num].v=min(tot,p[i-].r-p[i-].l+);
tot=;
}
}
sort(q+,q+num+,cmp2);
for(int i=;i<=num;i++){
int l=,r=i-;
while(l<r){
int mid=(l+r+)>>;
if(q[mid].r<q[i].l)l=mid;
else r=mid-;
}
nxt[i]=l;
}
for(int i=;i<=num;i++){
f[i]=max(f[i-],f[nxt[i]]+q[i].v);
}
printf("%d\n",n-f[num]);
}
吐槽：我前面基本都想到了，连判断矛盾的dp都想到了，真的就两个人之间要怎么判断是否矛盾没想到了。
当然可以按照我的思路来做，也可以转化为l和r来做，相比较来说后者更不好想，但理解起来更简单。
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++