扫描购物网站建设,做公章网站,网站建设发展制度,猎豹加速器现在看这题居然直接秒了。。。去年看的时候还以为神题。。 设以第i项为结尾的lis前缀为f[i]#xff0c;以第j项为结尾的lis后缀为g[i]#xff0c;如果求出f[i]和g[j]#xff0c;然后枚举i#xff0c;快速找到最大的满足a[j]a[i]的g[j]就可以了。注意到如果将f[i]从后往…现在看这题居然直接秒了。。。去年看的时候还以为神题。。 设以第i项为结尾的lis前缀为f[i]以第j项为结尾的lis后缀为g[i]如果求出f[i]和g[j]然后枚举i快速找到最大的满足a[j]a[i]的g[j]就可以了。注意到如果将f[i]从后往前枚举那么只要添加g[j]而不用删除操作了因此枚举f[i]在线段树中找(a[i]1,Xn]中g的最大值就可以了ansf[i]max(g[j]) (a[j]a[i]且jiL)然后顺势把g[j]插入线段树。 求f[i]也是dp线段树优化f[i]max(f[j])1 (a[j]a[i])。 #includeiostream
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#define REP(i,a,b) for(int ia;ib;i)
#define MS0(a) memset(a,0,sizeof(a))
#define key_val ch[ch[rt[i]][1]][0]
#define lson l,m,rt1
#define rson m1,r,rt1|1using namespace std;typedef long long ll;
const int maxn1000100;
const int INF1e910;int n,L;
int a[maxn],X[maxn],Xn;
int f[maxn],g[maxn];
int Max[maxn2];void push_up(int rt)
{Max[rt]max(Max[rt1],Max[rt1|1]);
}void build(int l,int r,int rt)
{if(lr){Max[rt]0;return;}int m(lr)1;build(lson);build(rson);push_up(rt);
}void update(int p,int c,int l,int r,int rt)
{if(lr){Max[rt]max(Max[rt],c);return;}int m(lr)1;if(pm) update(p,c,lson);else update(p,c,rson);push_up(rt);
}int query(int L,int R,int l,int r,int rt)
{if(LR) return 0;if(LlrR) return Max[rt];int m(lr)1;int res0;if(Lm) resmax(res,query(L,R,lson));if(Rm) resmax(res,query(L,R,rson));return res;
}int main()
{#ifndef ONLINE_JUDGEfreopen(in.txt,r,stdin);#endifint T;cinT;REP(casen,1,T){scanf(%d%d,n,L);REP(i,1,n) scanf(%d,a[i]),X[i]a[i];sort(X1,Xn1);Xnunique(X1,Xn1)-(X1);REP(i,1,n) a[i]lower_bound(X1,XXn1,a[i])-X;build(1,Xn,1);f[0]0;REP(i,1,n) f[i]query(1,a[i]-1,1,Xn,1)1,update(a[i],f[i],1,Xn,1);build(1,Xn,1);int ans0,tmp0;for(int in;i1;i--){int ji-L;if(j0){tmpf[j]query(a[j]1,Xn,1,Xn,1);ansmax(ans,tmp);}g[i]query(a[i]1,Xn,1,Xn,1)1;update(a[i],g[i],1,Xn,1);}printf(Case #%d: %d\n,casen,ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/--560/p/5211163.html
