本文共 1712 字，大约阅读时间需要 5 分钟。
传送门：
题意：有n个数，求间距大于d的最长上升序列。
分析：dp[i]表示在i点以a[i]结束距离大于d的最长上升序列，然后每更新到第i点时，取i-d之前小于a[i]的数为结束的最长上升序列进行状态转移，并维护前i-d之前的最大上升序列，维护i-d之前的每点为结束的最长上升序列用线段树维护即可。
#pragma comment(linker,"/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-6#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PII pair using namespace std;inline int read(){ char ch=getchar(); int x=0; while(ch>'9'||ch<'0')ch=getchar(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}int dp[N],a[N];int mx[N<<2];void pushup(int rt){ int ls=rt<<1,rs=ls|1; mx[rt]=max(mx[ls],mx[rs]);}void build(int l,int r,int rt){ mx[rt]=0; if(l==r)return; int m=(l+r)>>1; build(lson); build(rson);}void update(int pos,int c,int l,int r,int rt){ if(l==r) { mx[rt]=max(mx[rt],c); return; } int m=(l+r)>>1; if(pos<=m)update(pos,c,lson); else update(pos,c,rson); pushup(rt);}int query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) return mx[rt]; int m=(l+r)>>1; int res=0; if(L<=m)res=max(res,query(L,R,lson)); if(m 0) { build(0,N,1); for(int i=1;i<=n;i++)dp[i]=1; int ans=1; for(int i=1;i<=n&&i<=d;i++) { //scanf("%d",&a[i]); a[i]=read(); } for(int i=d+1;i<=n;i++) { //scanf("%d",&a[i]); a[i]=read(); if(a[i]>0)dp[i]=query(0,a[i]-1,0,N,1)+1; else dp[i]=1; update(a[i-d],dp[i-d],0,N,1); ans=max(ans,dp[i]); } printf("%d\n",ans); }}
转载于:https://www.cnblogs.com/lienus/p/4292309.html
