BZOJ1046 [HAOI2007]上升序列

题意

​   对于一个给定的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.

题解

O(N2)O(N^2)求出LIS数组f,然后贪心。一算复杂度好低呀,都不用nlognn log n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
namespace IO{
#define getch getchar
LL read(){LL T = 0,f = 1;char c = getch();while ((c<'0'||c>'9')&&c!='-') c=getch();if(c=='-')f=-1,c=getch();while (c>='0'&&c<='9'){T=((T<<1)+(T<<3))+c-48;c=getch();}return T*f;}
inline void write(LL x){if(x < 0) putchar('0'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
};
#define pc putchar
using namespace IO;
const int maxn = 10005;
int n,a[maxn],f[maxn];
void solve(int x){
int last = 0;
for (int i=1;i<=n;i++){
if (f[i] >= x && a[i] > last){
printf("%d",a[i]);
if (x!=1) pc(' ');
last = a[i];
x--;
if (!x) break;
}
}
puts("");
}
int main(){
n = read();
for (int i=1;i<=n;i++){
a[i] = read();
}
int len = 0;
for (int i=n;i>=1;i--){
f[i] = 0;
for (int j=i+1;j<=n;j++)
if (a[i] < a[j])
f[i] = max(f[i],f[j]);
f[i]++;
len = max(len,f[i]);
}
int Q = read();
while (Q--){
int mark = 0;
int x = read();
if (x>len) puts("Impossible"); else{
solve(x);
}
}
return 0;
}
文章目录
  1. 1. 题意
  2. 2. 题解