bzoj1046

反向做最长下降子序列+贪心就行了（不过这数据我觉得n2能a）(果然n2a了。。。。）

 1 #include<bits/stdc++.h>
 2 #define lowbit(a) ((a)&(-(a)))
 3 #define clr(a,x) memset(a,x,sizeof(a))
 4 #define rep(i,l,r) for(int i=l;i<(r);i++)
 5 #define down(i,r,l) for(int i=r;i>=(l);i--)
 6 typedef long long ll;
 7 using namespace std;
 8 int read()
 9 {
10     char c=getchar();
11     int ans=0,f=1;
12     while(!isdigit(c)){
13         if(c=='-') f=-1;
14         c=getchar();
15     }
16     while(isdigit(c)){
17         ans=ans*10+c-'0';
18         c=getchar();
19     }
20     return ans*f;
21 }
22 const int maxn=10009,maxm=1009,inf=0x7fffffff;
23 int n,m,a[maxn],g[maxn],d[maxn];
24 int lowerbound(int l,int r,int a){
25     if(l==r) return l;
26     int mid=(l+r)>>1;
27     return g[mid]<=a?lowerbound(l,mid,a):lowerbound(mid+1,r,a);
28 }
29 int main()
30 {    
31     n=read();
32     rep(i,0,n) a[i]=read(),g[i+1]=-inf;
33     down(i,n-1,0){
34         int p=lowerbound(1,n,a[i]);
35         d[i]=p;
36         g[p]=a[i];
37     }
38     m=read();
39     while(m--){
40         int l=read();
41         if(g[l]==-inf) puts("Impossible");
42         else{
43             int last=-inf;
44             rep(i,0,n){
45                 if(d[i]>=l&&a[i]>last){
46                     printf("%d",a[i]);
47                     last=a[i];
48                     if(!--l) break;
49                     printf(" ");
50                 }
51             }
52             puts("");
53         }
54     }
55     return 0;
56 }

View Code

1046: [HAOI2007]上升序列

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3084 Solved: 1040
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

6
3 4 1 2 3 6
3
6
4
5

Sample Output

Impossible
1 2 3 6
Impossible

HINT

数据范围

N<=10000

M<=1000

Source

[Submit][Status][Discuss]