> the first question is a mess.
> what can be inherited from the current location DP?
First the position in front of themselves, and then the value is smaller than their own, and because the building blocks in front of it were pushed it affected I was also affected, the building blocks between us were pushed I was affected it was okay, so it is farther from the correct position than I want to be.Small is the only thing that can be done if the distance is negative.
written out is J & lt; I & amp; & amp; a [j] & lt; a [i] & amp; & amp; J-A [j] & lt; = I-A [i] three-dimensional partial order but in fact, if the latter two are satisfiedThe front one must be satisfied.
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int s[110000]; int lowbit(int x){return x&-x;} void change(int x,int k) { while(x<=100010) { s[x]=max(s[x],k); x+=lowbit(x); } } int getmax(int x) { int ret=0; while(x>0) { ret=max(ret,s[x]); x-=lowbit(x); } return ret; } struct node{int x,y;}a[110000]; bool cmp(node n1,node n2){return n1.x==n2.x?n1.y<n2.y:n1.x<n2.x;} int c[110000],lslen,ls[110000]; int f[110000]; int main() { freopen("klo.in","r",stdin); freopen("klo.out","w",stdout); int n,x; scanf("%d",&n);lslen=0; for(int i=1;i<=n;i++)scanf("%d",&c[i]); int tp=0; for(int i=1;i<=n;i++) { a[++tp].x=i-c[i],a[tp].y=c[i]; if(a[tp].x<0)tp--; } n=tp; sort(a+1,a+n+1,cmp); int ans=0; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { int mx=getmax(a[i].y-1); f[i]=mx+1; ans=max(ans,f[i]); change(a[i].y,f[i]); } printf("%d\n",ans); return 0; }