发现每一次 $[b[i]+1,n-a[i]]$ 这个区间的分数必须相同,否则不合法.
而一个相同的区间 $[l,r]$ 最多只能出现区间长度次.
于是,就得到了一个 $dp:$ 将每一种区间的出现次数看作是价值,要选出若干个互不相交的区间使得价值最大.
这个直接用树状数组优化 dp 跑一下就行了~
#include <bits/stdc++.h>
#define N 100004
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,C[N],f[N];
struct P
{
int l,r,v;
P(int l=0,int r=0,int v=0):l(l),r(r),v(v){}
}p[N],g[N];
bool cmp(P a,P b)
{
return a.l==b.l?a.r<b.r:a.l<b.l;
}
bool cmp2(P a,P b)
{
return a.r<b.r;
}
int lowbit(int t)
{
return t&(-t);
}
void update(int x,int d)
{
for(;x<N;x+=lowbit(x)) C[x]=max(C[x], d);
}
int query(int x)
{
int tmp=0;
for(;x>0;x-=lowbit(x)) tmp=max(tmp, C[x]);
return tmp;
}
int main()
{
int i,j,tot=0;
// setIO("input");
scanf("%d",&n);
for(i=1;i<=n;++i)
{
int a,b,l,r;
scanf("%d%d",&a,&b);
l=b+1,r=n-a;
if(l<=r)
{
p[++tot]=P(l,r,0);
}
}
sort(p+1,p+1+tot,cmp);
int pp=0,mx=0;
for(i=1;i<=tot;i=j)
{
++pp;
g[pp]=p[i];
for(j=i;j<=tot&&p[j].l==p[i].l&&p[j].r==p[i].r;++j)
{
++g[pp].v;
}
g[pp].v=min(g[pp].v, g[pp].r-g[pp].l+1);
}
sort(g+1,g+1+pp,cmp2);
for(i=1;i<=pp;++i)
{
// printf("%d %d %d\n",g[i].l,g[i].r,g[i].v);
f[i]=g[i].v+query(g[i].l-1);
update(g[i].r, f[i]);
mx=max(mx, f[i]);
}
printf("%d\n",n-query(n));
return 0;
}