【DP】BZOJ2298 [HAOI2011]problem a

题面在这里

首先吐槽一下题意表述不清……

题目的意思是每个人说恰好有\(a_i\)个人排在前面，恰好\(b_i\)人排在后面

一开始把”有“理解为“存在”了，想了好久……

那么就可以直接确定每个人的排名区间了

如果有两个区间相交但不重合，就可以判定至少一人说谎

问题就变成了最简单的区间覆盖问题了，区间的权值是相同区间的个数

示例程序：

#include<cstdio>
#include<algorithm>
#define mp make_pair
#define X first
#define Y second
using namespace std;
inline char nc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int red(){
	int res=0,f=1;char ch=nc();
	while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
	while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
	return res*f;
}

const int maxn=100005;
int n,m,f[maxn];
pair<int,int> a[maxn];
int tot,lnk[maxn],nxt[maxn],son[maxn],w[maxn];
inline void add(int x,int y,int z){
	z=min(z,x-y);
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;w[tot]=z;
}
int main(){
	n=red();
	for (int i=1,x,y;i<=n;i++){
		x=red(),y=red();
		if (x+y+1<=n) a[++m]=mp(x+1,n-y);
	}
	sort(a+1,a+1+m);
	{
		int x=1;
		for (int i=2;i<=m;i++)
		 if (a[i]==a[i-1]) x++;else add(a[i-1].Y,a[i-1].X-1,x),x=1;
		add(a[m].Y,a[m].X-1,x);
	}
	f[0]=0;
	for (int i=1;i<=n;i++){
		f[i]=f[i-1];
		for (int j=lnk[i];j;j=nxt[j])
		 f[i]=max(f[i],f[son[j]]+w[j]);
	}
	printf("%d",n-f[n]);
	return 0;
}