题目名称 312. [HAOI 2007]上升序列
输入输出 lis.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarBYVoid 于2009-04-09加入
开放分组 全部用户
提交状态
分类标签
HAOI 动态规划 分治 LIS
分享题解
通过:221, 提交:585, 通过率:37.78%
Gravatarkaaala 100 0.802 s 0.47 MiB C++
Gravatarnew ioer 100 0.855 s 0.44 MiB C++
GravatarHale 100 0.855 s 4.30 MiB C++
Gravatar森林 100 0.860 s 0.43 MiB C++
Gravatar森林 100 0.884 s 0.38 MiB C++
Gravatar河北交通广播992大师来了 100 0.917 s 0.43 MiB C++
Gravatar面对疾风吧 疾风 疾风吧 100 0.918 s 0.26 MiB C++
GravatarNewBee 100 0.921 s 0.36 MiB C++
Gravatar_Itachi 100 0.932 s 0.40 MiB C++
Gravatardigital-T 100 0.934 s 0.40 MiB C++
本题关联比赛
假期找点事儿做题吧
关于 上升序列 的近10条评论(全部评论)
同各位楼上
Gravatar夜莺
2020-03-16 17:23 8楼
同各位楼上
GravatarHZOI_蒟蒻一只
2017-09-11 11:59 7楼
同上和上上和上上上
Gravatar_Itachi
2016-08-09 16:21 6楼
卡了一分钟
GravatarSky_miner
2016-08-09 15:39 5楼
好不容易才水过......
Gravatar神利·代目
2015-10-03 06:19 4楼
Gravatar0-0
2014-08-25 21:59 3楼
卡了一分半
GravatarMongo
2014-04-10 09:07 2楼
评测的时候卡了一分钟……
Gravatarcstdio
2013-03-08 19:34 1楼

312. [HAOI 2007]上升序列

★★☆   输入文件:lis.in   输出文件:lis.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

对于一个给定的$S$ = {$a_1$,$a_2$,$a_3$,…,$a_n$},若有$P$ = {$a_{x1}$,$a_{x2}$,$a_{x3}$,…,$a_{xm}$}满足($x_1$<$x_2$<…$x_m$)且($a_{x1}$<$a_{x2}$<…$a_{xm}$)。那么就称$P$为$S$的一个上升序列。如果有多个$P$满足条件,那么我们想求字典序最小的那个。 任务 给出$S$序列,给出若干询问。对于第$i$个询问,求出长度为$L_i$的上升序列,如有多个,求出字典序最小的那个(即首先$x_1$最小,如果不唯一,再看$x_2$最小……),如果不存在长度为$L_i$的上升序列,则打印$Impossible$.

【输入格式】

第一行一个$N$,表示序列一共有$N$个元素;

第二行$N$个数,为$a_1$,$a_2$,…,$a_n$;

第三行一个$M$,表示询问次数。下面接$M$行每行一个数$L$,表示要询问长度为$L$的上升序列;

【输出格式】

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

【样例输入】

6
3 4 1 2 3 6
3
6
4
5

【样例输出】

Impossible
1 2 3 6
Impossible 

【数据范围】

$100$%的数据,$1<=N<=10000\ 1<=M<=1000$;

【来源】

$HAOI$ $COGS$