考虑暴力dp。
设\(dp_i\)表示前\(i\)个积木,保留积木\(i\)的最大答案。
那么有
\(dp_i=max(dp_j)+1(i>j,a_i>a_j,a_i-a_j\le i-j)\)
对\(j\)的限制条件里前2条显然,后一条是因为要使积木\(i\)和\(j\)之间有足够的积木使它们的相对位置正确。
由第三条可得\(i-a_i\ge j-a_j\)
那么就是一个三维偏序?
其实不是。由\(a_i>a_j,i-a_i\ge j-a_j\)可得\(i>j\)。
所以其实是一个二维偏序。
我们一开始记录\(v_i=i-a_i\),然后按\(a_i\)排序每次在线段树上查找\(v\)比\(v_i\)小的,\(dp\)的最大值用来更新答案,将\(dp_i\)加入线段树即可。
当然用树状数组也可以做。
code:
#include<bits/stdc++.h>
#define ci const int&
#define Upd(x) (t[x].mx=max(t[x<<1].mx,t[x<<1|1].mx))
using namespace std;
const int lim=1e6;
struct node{
int l,r,mx;
}t[4000010];
struct CMP{
int v1,v2;
}c[100010];
int n,h,sz,dp,ans;
bool cmp(CMP x,CMP y){
return x.v1==y.v1?x.v2>y.v2:x.v1<y.v1;
}
void Build(ci x,ci l,ci r){
t[x].l=l,t[x].r=r;
if(l==r)return;
int mid=l+r>>1;
Build(x<<1,l,mid),Build(x<<1|1,mid+1,r);
}
void Change(ci x,ci d,ci v){
if(t[x].l==t[x].r)return(void)(t[x].mx=max(t[x].mx,v));
int mid=t[x].l+t[x].r>>1;
d<=mid?Change(x<<1,d,v):Change(x<<1|1,d,v),Upd(x);
}
int Query(int x,int l,int r){
if(t[x].l==l&&t[x].r==r)return t[x].mx;
int mid=t[x].l+t[x].r>>1;
return r<=mid?Query(x<<1,l,r):(l>mid?Query(x<<1|1,l,r):max(Query(x<<1,l,mid),Query(x<<1|1,mid+1,r)));
}
int main(){
scanf("%d",&n);
Build(1,0,lim);
for(int i=1;i<=n;++i)scanf("%d",&h),i>=h?c[++sz]=(CMP){h,i-h},0:0;
sort(c+1,c+sz+1,cmp);
for(int i=1;i<=sz;++i)dp=Query(1,0,c[i].v2)+1,ans=max(ans,dp),Change(1,c[i].v2,dp);
printf("%d",ans);
return 0;
}