https://www.lydsy.com/JudgeOnline/problem.php?id=2298
https://www.luogu.org/problemnew/show/P2519
一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)
好题啊，以及我的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+5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),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=1,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=1;i<=n;i++){ int a=read(),b=read(); if(a+b+1>n)continue; p[++cnt].l=a+1;p[cnt].r=n-b; } sort(p+1,p+cnt+1,cmp1); for(int i=2;i<=cnt+1;i++){ if(p[i].l==p[i-1].l&&p[i].r==p[i-1].r)tot++; else{ q[++num].l=p[i-1].l;q[num].r=p[i-1].r; q[num].v=min(tot,p[i-1].r-p[i-1].l+1); tot=1; } } sort(q+1,q+num+1,cmp2); for(int i=1;i<=num;i++){ int l=0,r=i-1; while(l<r){ int mid=(l+r+1)>>1; if(q[mid].r<q[i].l)l=mid; else r=mid-1; } nxt[i]=l; } for(int i=1;i<=num;i++){ f[i]=max(f[i-1],f[nxt[i]]+q[i].v); } printf("%d ",n-f[num]); }
吐槽：我前面基本都想到了，连判断矛盾的dp都想到了，真的就两个人之间要怎么判断是否矛盾没想到了。
当然可以按照我的思路来做，也可以转化为l和r来做，相比较来说后者更不好想，但理解起来更简单。
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++