随便推推，发现要求求a[i]-i单调不降，a[i]单调递增的最长子序列
然后发现这两个条件可以推出i<j
所以改变一下坐标然后求最长上升子序列即可
注意双关键字排序
注意吧a[i]-i>0的都continue了
#include<iostream> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<cstdlib> #include<cstdio> #include<map> #include<bitset> #include<set> #include<stack> #include<vector> #include<queue> using namespace std; #define MAXN 100010 #define MAXM 1000010 #define ll long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 #define lb(x) x&-x struct data{ int x; int y; friend bool operator <(data x,data y){ return x.x!=y.x?x.x>y.x:x.y<y.y; } }; data a[MAXN]; int n; int c[MAXM]; int ans; void change(int x,int y){ for(;x<MAXM;x+=lb(x)){ c[x]=max(c[x],y); } } int ask(int x){ int re=0; for(;x;x-=lb(x)){ re=max(re,c[x]); } return re; } int main(){ int i,x; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&x); a[i].x=x-i; a[i].y=x; } sort(a+1,a+n+1); for(i=1;i<=n;i++){ if(a[i].x>0){ continue ; } x=ask(a[i].y-1)+1; ans=max(ans,x); change(a[i].y,x); } printf("%d\n",ans); return 0; } /* */
