为啥我考虑了DP考虑了cdq就没考虑考虑两个合起来哩
这个题首先一看就很乱搞。。。
容易想到自己的值减去下标。。。
那么当前位置DP的话能继承什么呢？
首先位置要在自己前面，然后值要比自己小，还有，因为它前面的积木被推了它受影响我也受影响，我们之间的积木被推了我受影响它没事，所以它距离正确位置的距离要比我要小才行，当然假如这个距离是负数就不能到达，去掉这个状态。
写出来就是j<i&&a[j]<a[i]&&j-a[j]<=i-a[i]三维偏序 但是其实吧，假如满足后两个，前面那个也肯定满足的。。
#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 ",ans); return 0; }