BZOJ1046【HAOI2007】上升序列 < DP >

Problem

【HAOI2007】上升序列

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

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

Input

第一行一个$N$，表示序列一共有$N$个元素第二行$N$个数，为$a_1,a_2,\cdots,a_n$ 第三行一个$M$，表示询问次数。下面接$M$行每行一个数$L$，表示要询问长度为$L$的上升序列。$N\le 10000$，$M\le 1000$

Output

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

Sample Input

6
3 4 1 2 3 6
3
6
4
5

Sample Output

Impossible
1 2 3 6
Impossible

标签：DP

Solution

一道$LIS$的变形。
显然需要先预处理出每个数向后能组成的$LIS$的最大长度。
对于每次询问，从前往后取，一旦某数字的$LIS$最大长度比$len$大，则此数可加入答案。顺序构造即可。

Code

#include <iostream>
#include <cstdio>
#define MAX_N 10000
using namespace std;
int n, m, k, a[MAX_N+5], f[MAX_N+5];
void print() {
    for (int i = 1, pre = 0; i <= n; i++)
        if (f[i] >= k && a[i] > pre) {
            printf("%d", a[i]), pre = a[i];
            if (--k)	printf(" ");
            else	break;
        }
    if (k)	printf("Impossible");	printf("\n");
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)	scanf("%d", &a[i]), f[i] = 1;
    for (int i = n; i >= 1; i--)	for (int j = i+1; j <= n; j++)	if (a[i] < a[j])	f[i] = max(f[i], f[j]+1);
    scanf("%d", &m);
    while (m--)	scanf("%d", &k), print();
    return 0;
}