1046: [HAOI2007]上升序列
Time Limit: 10 Sec Memory Limit: 162 MB
Description
對于一個給定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},滿足(x1 < x2 < … < xm)且（ ax1 < ax
2 < … < axm)。那麼就稱P為S的一個上升序列。如果有多個P滿足條件，那麼我們想求字典序最小的那個。任務給
出S序列，給出若幹詢問。對于第i個詢問，求出長度為Li的上升序列，如有多個，求出字典序最小的那個（即首先
x1最小，如果不唯一，再看x2最小……），如果不存在長度為Li的上升序列，則列印Impossible.
Input
第一行一個N，表示序列一共有N個元素第二行N個數，為a1,a2,…,an 第三行一個M，表示詢問次數。下面接M
行每行一個數L，表示要詢問長度為L的上升序列。N<=10000，M<=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求最長下降序列, 求出到每個點的最大長度。 這樣對于一個長度為L的序列，我們從頭往後掃，如果目前位置滿足條件，他就可以加入到序列當中 滿足的條件是 ： f[i] >= 剩餘長度 && a[i] < a[last]
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <algorithm>
5 #define LL long long
6
7 using namespace std;
8
9 const int MAXN = 1e5 + 10;
10 int N, M;
11 LL a[MAXN];
12 LL b[MAXN];
13 LL f[MAXN];
14 inline LL read()
15 {
16 LL x = 0, w = 1; char ch = 0;
17 while(ch < '0' || ch > '9') {
18 if(ch == '-') {
19 w = -1;
20 }
21 ch = getchar();
22 }
23 while(ch >= '0' && ch <= '9') {
24 x = x * 10 + ch - '0';
25 ch = getchar();
26 }
27 return x * w;
28 }
29
30 int main()
31 {
32 N = read();
33 for(int i = 1; i <= N; i++) {
34 a[i] = read() * -1;
35 }
36 LL cnt = 0;
37 for(int i = N; i >= 1; i--) {
38 int k = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
39 f[i] = k;
40 if(k > cnt) {
41 cnt++;
42 }
43 b[k] = a[i];
44 a[i] = a[i] * -1;
45 }
46 /*f[N] = 1;
47 cout<<f[N]<<endl;
48 for(int i = N - 1; i >= 1; i--) {
49 for(int j = i + 1; j <= N; j++) {
50 if(a[j] > a[i]) {
51 f[i] = max(f[i], f[j] + 1);
52 }
53 }
54 cnt = max(cnt, f[i]);
55 cout<<f[i]<<endl;
56 }
57 return 0;*/
58 M = read();
59 for(int i = 1; i <= M; i++) {
60 int len = read();
61 LL last = -1e9;
62 if(len > cnt) {
63 printf("Impossible");
64 } else {
65 for(int j = 1; j <= N; j++) {
66 if(f[j] >= len && a[j] > last) {
67 len--;
68 last = a[j];
69 printf("%lld", a[j]);
70 if(len > 0) {
71 printf(" ");
72 }
73 if(len == 0) {
74 break;
75 }
76 }
77 }
78 }
79 printf("\n");
80 }
81 return 0;
82 }
83
84 /*
85
86 6
87 3 4 1 2 3 6
88 3
89 6
90 4
91 3
92
93
94 */ View Code
轉載于:https://www.cnblogs.com/wuenze/p/8570406.html