Bzoj1046 [HAOI2007]上升序列-白红宇

Bzoj1046 [HAOI2007]上升序列

阅读量：6657 次

发布时间：2019-06-25

本文共 1546 字，大约阅读时间需要 5 分钟。

1046: [HAOI2007]上升序列

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 4245 Solved: 1447

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

3 4 1 2 3 6

Sample Output

Impossible

1 2 3 6

Impossible

HINT

Source

要求字典序最小，且有多次询问。

转换思路，反向求最长下降序列，则求出的序列满足字典序最小。倒序时每个位置的“最长下降长度”相当于正序时的“最长可上升长度”

对于每次询问，从“最长可上升长度”大于等于目标长度的位置开始查找，依次输出答案即可。

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 using namespace std; 9 const int mxn=100010;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 int n,a[mxn];17 int f[mxn];18 int d[mxn],len;19 int find(int x){20 int l=1,r=len;21 while(l<=r){22 int mid=(l+r)>>1;23 if(d[mid]<=x)r=mid-1;24 else l=mid+1;25 }26 return l;27 }28 void dp(){29 d[0]=1e9;30 for(int i=n;i>0;--i){31 if(a[i]
           
            len){52 printf("Impossible\n");53 continue;54 }55 int last=0;56 for(i=1;i<=n && op;i++){57 if(f[i]>=op && last