【gzoj8.12综合三】银河摆渡【二分+DP】

题意&分析

初看感觉自己没能很好地理解题意，被故事带跑了，一直在往“交叉”“逆序对”等词语方面想，需要先将题目抽象化，看到想让你求什么。

观察到 $i<j且a[i]<a[j]$的航线就可以同时建立，其实这就是上升子序列的形式，所以这题求的就是最长上升子序列。

于是乎我花10min敲完了$n^2$的代码交上去直接T。。。看到数据是10⁶，就开始想n logn的做法。

这个算法就是要让整个序列的字典序尽量小，因为如果长度是一样的，放个小的数变长的机会就更多，不管哪个位置。

所以我们在长度不变的情况下做操作，具体地，考虑最新的一个数能放到哪个位置，只需要在前面找到第一个比ta大的数并且插入进去，序列单调性不改变，且为更新提供更多机会。比如：2 5 7，现在进来一个3，只需要将5变成3，在3,7之间空间就更大了，又进来一个4，变成2 3 4，这样就可以看出来，如果一开始3不替换5，那么此时的序列就会是2 4 7，显然不如2 3 4优（想想进来个6会是什么情况）。

这个前面找到第一个比ta大的数的操作，通过二分查找(upper_bound)实现，其实就是log级别了。

上代码

$O(n^2)$

#include
#include
#include
using namespace std;

long long n,a[1010000],f[1010000];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		f[i]=1;
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=i-1;j++)
		{
			if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
		}
	}
	long long mx=0;
	for(int i=1;i<=n;i++) mx=max(mx,f[i]);
	cout<<mx;
	return 0;
} 
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

$O(n\ast logn)$

#include
#include
#include
using namespace std;

int n,f[1000010],a[1000010],len;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		if(a[i]>f[len]) 
		{
			f[++len]=a[i];
		}
		else
		{
			int t=upper_bound(f,f+len,a[i])-f;
			f[t]=a[i];
		}
	}
	cout<<len;
 	return 0;
}
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