BZOJ1046【HAOI2007】上升序列 < DP >

Problem

【HAOI2007】上升序列

Description

对于一个给定的,若有,满足()且()。那么就称为的一个上升序列。如果有多个满足条件，那么我们想求字典序最小的那个。任务给出序列，给出若干询问。对于第个询问，求出长度为的上升序列，如有多个，求出字典序最小的那个（即首先最小，如果不唯一，再看最小……），如果不存在长度为的上升序列，则输出.

Input

第一行一个，表示序列一共有个元素第二行个数，为第三行一个，表示询问次数。下面接行每行一个数，表示要询问长度为的上升序列。，

Output

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

Sample Input

6
3 4 1 2 3 6
3
6
4
5

Sample Output

1
2
3

Impossible
1 2 3 6
Impossible

标签：DP

Solution

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

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;
}