题目连接

bz链接

我们发现，如果一个人有ai个分数比他高的人，有bi个分数比他低的人

那么按照分数排序后，区间[ai+1,n-bi]中的人分数便是相同的

这样就将一个人转化为一个区间

也许有很多人的区间都是[x,y]所以我们令区间[x,y]的权值为这个区间的人数，即ai+1=x，n-bi=y的人的个数

注意到权值如果大于区间长度不符合，于是要与y-x+1取max

我们取这个区间，表示这个区间的人说的是真话

现在问题转化为求多个不相交的区间，使得权值和最大，这样dp一下就好了

用f[i]表示到i位置的最大权值，f[i]=max(f[l-1],f[i-1])

# include

include

include

include

include

include

using namespace std;
const int mn = ;
struct edge{int to,dis,next;};
edge e[mn];
int head[mn],edge_max;
void add(int x,int y,int z)
{
//printf("%d %d %d\n",x,y,z);
e[++edge_max].to=y;
e[edge_max].dis=z;
e[edge_max].next=head[x];
head[x]=edge_max;
}
struct person{int a,b;};
person c[mn],d[mn];
int f[mn],tot,cnt;
bool cmp(person x,person y)
{
if(x.b==y.b) return x.ay) continue;
else d[++tot].a=x,d[tot].b=y;
}
sort(d+,d++tot,cmp);
/*for(int i=1;i<=tot;i++) printf("%d %d\n",d[i].a,d[i].b);*/ int now=,N=d[tot].b; for(int i=;i<=tot;i++) { now++; if(d[i].a!=d[i+].a || d[i].b!=d[i+].b){ if(now>=d[i].b-d[i].a+)
now=d[i].b-d[i].a+;
add(d[i].b,d[i].a,now);
now=;
}
}
for(int i=;i<=N;i++)
{
f[i]=f[i-];
for(int j=head[i];j;j=e[j].next)
f[i]=max(f[i],f[e[j].to-]+e[j].dis);
}
printf("%d",n-f[N]);
return ;
}