BZOJ 1046 上升序列

发表于 | 更新于

Link

读错题了。。NAIVE。要求得是下标字典序最小，以为是值字典序最小。不过看看Discuss区，好像不少人也被坑了。。

Solution

字典序受靠前的影响最大，所以就可以贪心，贪心出来一定是最优的。就类似01串在可持久化Trie上匹配最大的异或值一样。 给了一个长度LL，如何判断可行并构造一组在原序列中“最靠前”的可行解？也就是说，从前向后枚举，如何判断第ii个位置的数字能否被加入答案？显然，如果以这个点为起点可以构成一个长度为LL的LIS，那这个点就可以取，而且由于是从前向后枚举，取这个字典序肯定是最小的。 倒过来求出来LDS，然后从前向后构造最优解。

Tips

一定要把题目读对。。把给的条件中每个量的含义都弄清。。不能想当然

Code

不过话说，我只引入了upper_bound，为什么也可以用lower_bound而不会报错？？ 

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=10000+10;
using std::upper_bound;
using std::greater;
int main()
{
	freopen("input","r",stdin);
	static int f[MAXN],a[MAXN],next[MAXN],lis[MAXN];
	int n,ANS=0;get(n);
	for(int i=1;i<=n;i++) get(a[i]);
	for(int i=n;i;i--)
	{
		int p=lower_bound(lis+1,lis+1+n,a[i],greater<int>())-lis;
		f[i]=p;
		chkmx(lis[p],a[i]);
		chkmx(ANS,f[i]);
	}
	int m;get(m);
	for(int i=1;i<=m;i++)
	{
		int x;get(x);
		if(x>ANS) puts("Impossible");
		else
		{
			for(int j=1,p=0;j<=n && x;j++)
				if(f[j]>=x && a[j]>a[p])
					printf("%d%s",a[p=j],--x?" ":"\n");
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */