小明系列问题——小明序列【线性dp】

传送门 这题可以用$O(nlogn)$的最长上升子序列算法做，经典的$nlogn$算法是间隔大于0的算法，那么这题就是这个算法的扩展，取出的每个数的下标差大于d。那么我们只要算到i的时候，先记录下已经形成的c[]函数第一个大于等于a[i]的数的下标，然后用$dp[j]$记录下来，然后在算到$i+d$的时候，把它更新进去，那么对于每个数j就避免了$j-d,j-d+2...j-1$的影响。

#include<bits/stdc++.h> using namespace std; const int N=100000+5; int a[N],c[N],dp[N]; int n,d; #define gc getchar int read(){ int res=0,f=1;char ch=gc(); while(!isdigit(ch)) f^=ch=='-',ch=gc(); while(isdigit(ch)) res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } int main(){ while(scanf("%d%d",&n,&d)!=EOF){ for(int i=1;i<=n;i++) a[i]=read(); memset(c,0x3f3f,sizeof(c)); int ans=1,maxx=1; for(int i=1;i<=n;i++){ dp[i]=lower_bound(c+1,c+1+n,a[i])-c; maxx=max(maxx,dp[i]); int j=i-d; if(j>=1&&c[dp[j]]>a[j]){ c[dp[j]]=a[j]; } } printf("%d\n",maxx); } }