[bzoj1046][DP][乱搞]上升序列

本文主要是介绍[bzoj1046][DP][乱搞]上升序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … <
xm)且（ ax1 < ax 2 < … <
axm)。那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。任务给
出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先
x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.

Input

第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an 第三行一个M，表示询问次数。下面接M
行每行一个数L，表示要询问长度为L的上升序列。N<=10000，M<=1000

Output

对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.

Sample Input

6

3 4 1 2 3 6

3

6

4

5

Sample Output

Impossible

1 2 3 6

Impossible

题解

啊一开始只会$n^{2}log$的…
预处理一个向前向后的LIS
从前往后填数
设往前的LIS是f1[i]，往后的LIS是f2[i]，当前填了的长度是len
如果len+f2[i]-1>=L，那么这个数显然可填
填上就好了…

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define zero 10005
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
}
inline void print(int x){write(x);printf(" ");}
struct LSnode{int y,p;}w[11000];int tt;
bool LScmp(LSnode n1,LSnode n2){return n1.y<n2.y;}
int nxt[11000],f1[11000],f2[11000],cal[11000],n,m,L;
int s[41000],fac[41000];
int lowbit(int x){return x&-x;}
void change(int x,int c){while(x<=40000)s[x]=max(s[x],c),x+=lowbit(x);}
int findmax(int x){int ret=0;while(x>=1)ret=max(ret,s[x]),x-=lowbit(x);return ret;}
int a[41000],alen;
int main()
{n=read();for(int i=1;i<=n;i++)w[i].y=read(),w[i].p=i;sort(w+1,w+1+n,LScmp);tt=1;cal[w[1].p]=tt;fac[tt]=w[1].y;for(int i=2;i<=n;i++){if(w[i].y!=w[i-1].y)tt++;cal[w[i].p]=tt;fac[tt]=w[i].y;}for(int i=1;i<=n;i++)f1[i]=findmax(cal[i]-1)+1,change(cal[i],f1[i]);memset(s,0,sizeof(s));for(int i=1;i<=n;i++)cal[i]=-cal[i];for(int i=n;i>=1;i--)f2[i]=findmax(cal[i]+zero-1)+1,change(cal[i]+zero,f2[i]);for(int i=1;i<=n;i++)cal[i]=-cal[i];m=read();while(m--){L=read();bool bk=false;for(int i=1;i<=n;i++)if(f1[i]>=L){bk=true;break;}if(!bk)puts("Impossible");else{alen=1;while(alen<=L){int la=cal[a[alen-1]];for(int i=a[alen-1]+1;i<=n;i++)if(cal[i]>la&&alen+f2[i]-1>=L){a[alen]=i;break;}alen++;}for(int i=1;i<alen;i++)print(fac[cal[a[i]]]);puts("");}}return 0;
}

这篇关于[bzoj1046][DP][乱搞]上升序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---