我们设f[i]为保留第i个木块最多的符合未知数
显然f[i]=max(f[j])+1 满足i>j a[i]>a[j] i-j>=a[i]-a[j]
我们把最后一个式子变成a[i]-i<=a[j]-j
三元关系很不好弄对吧,但仔细观察可知，由最后两个式子一定可以推出i>j
那不就水了，排序树状数组即可
1 var f,a,b:array[0..100010] of longint; 2 c:array[0..1000010] of longint; 3 i,n,ans:longint; 4 5 function max(a,b:longint):longint; 6 begin 7 if a>b then exit(a) else exit(b); 8 end; 9 10 function lowbit(x:longint):longint; 11 begin 12 exit(x and (-x)); 13 end; 14 15 procedure swap(var a,b:longint); 16 var c:longint; 17 begin 18 c:=a; 19 a:=b; 20 b:=c; 21 end; 22 23 procedure add(x,w:longint); 24 begin 25 while x<=n do 26 begin 27 c[x]:=max(c[x],w); 28 x:=x+lowbit(x); 29 end; 30 end; 31 32 function ask(x:longint):longint; 33 begin 34 ask:=0; 35 while x>0 do 36 begin 37 ask:=max(ask,c[x]); 38 x:=x-lowbit(x); 39 end; 40 end; 41 42 procedure sort(l,r:longint); 43 var y,i,j,x:longint; 44 begin 45 i:=l; 46 j:=r; 47 x:=a[(l+r) shr 1]; 48 y:=b[(l+r) shr 1]; 49 repeat 50 while (b[i]>y) or (b[i]=y) and (a[i]<x) do inc(i); 51 while (y>b[j]) or (b[j]=y) and (x<a[j]) do dec(j); 52 if not(i>j) then 53 begin 54 swap(a[i],a[j]); 55 swap(b[i],b[j]); 56 inc(i); 57 dec(j); 58 end; 59 until i>j; 60 if l<j then sort(l,j); 61 if i<r then sort(i,r); 62 end; 63 64 begin 65 readln(n); 66 for i:=1 to n do 67 begin 68 read(a[i]); 69 b[i]:=a[i]-i; 70 end; 71 sort(1,n); 72 for i:=1 to n do 73 begin 74 if b[i]>0 then continue; 75 f[i]:=ask(a[i]-1)+1; 76 ans:=max(f[i],ans); 77 add(a[i],f[i]); 78 end; 79 writeln(ans); 80 end.