1046: [HAOI2007]上升序列
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3671 Solved: 1255
[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
3 4 1 2 3 6
3
6
4
5
Sample Output
Impossible
1 2 3 6
Impossible
1 2 3 6
Impossible
HINT
数据范围
N<=10000
M<=1000
Source
题解：
二分＋递推
不会。。。
orz 黄学长 : http://hzwer.com/4065.html
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAXN 10010
int f[MAXN],a[MAXN],len[MAXN],mx,n,cc[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
int ef(int k)
{
int l=,r=mx,mid,ans=;
while(l<=r)
{
mid=(l+r)/;
if(f[mid]>k){ans=mid;l=mid+;}
else r=mid-;
}
return ans;
}
void print(int k)
{
int last=-,lc=,i;
for(i=;i<=n;i++)
{
if(len[i]>=k&&a[i]>last)
{
k--;
cc[++lc]=a[i];
last=a[i];
if(k==)break;
}
}
for(i=;i<lc;i++)printf("%d ",cc[i]);printf("%d",cc[lc]);
printf("\n");
}
int main()
{
int i,tmp,m,k,j;
n=read();
for(i=;i<=n;i++)a[i]=read();
memset(f,,sizeof(f));
memset(len,,sizeof(len));
mx=;
for(i=n;i>=;i--)
{
tmp=ef(a[i]);
len[i]=tmp+;
f[tmp+]=max(f[tmp+],a[i]);
mx=max(mx,tmp+);
}
m=read();
for(i=;i<=m;i++)
{
k=read();
if(k>mx)printf("Impossible\n");
else
{
print(k);
}
}
fclose(stdin);
fclose(stdout);
return ;
}