动态规划：最长上升子序列

碎碎念

前天复习dp时学习了一遍，本来觉得太简单了，没想写的，结果今天周赛的第四题直接给了道模板题，我还没默出来，罚了5分钟。赶紧复习一下
学习了加速cin的方法，怕忘了，先写在这里

ios::sync_with_stdio(false);

正文

Longest Increasing Subsequence，简称LIS。

给一串数字，找出子序列中最长的上升序列。

基础解法：

dp[i]表示以i结尾的最长上升子序列的长度，可以得到以下状态转移方程：

dp[i]从前项推导得出，遍历 1……i-1 ，找到比a[i]小，并且dp最大的j，在此基础上加一，即为模拟上升子序列的添加。

以导弹模拟为例题，此题分别要求求出最长非升子序列和最长升序子序列：

#include<iostream>
using namespace std;
int a[1 << 20];
int before[1 << 20];
int len[1 << 20];
int last[1 << 20], tot = 0, ans = 0;
int main() {
	int n = 0;
	while (cin >> a[++n]) {
		len[n] = 1;
		int distance = 1<<20;
		int mini = 1;
		for (int i = 1; i <= tot; i++) {
			if (a[n] <= last[i] && last[i] - a[n] < distance)
			{
				distance = last[i] - a[n];
				mini = i;
			}
		}
		if (distance == 1<<20) last[++tot] = a[n];
		else last[mini] = a[n];
		for (int i = n - 1; i >= 1; i--) {
			if (a[n] <= a[i]) if (len[n] <= len[i]) 
					len[n] = len[i] + 1;
			
		}
	}
	int maxi = 1;
	for (int i = 1; i <= n; i++) if (len[i] > len[maxi]) maxi = i;
	cout << len[maxi] << endl;
	cout << tot;
}

此种解法的时间复杂度为O(n²)，不足以解决1e5规模的问题，需要优化

优化解法

这篇博客写的非常好。参考了一下。

工具介绍

引入了STL的lower_bound与up_bound。两者用法基本一致：

在顺序序列里，查找的是第一个大于等于该元素的元素（upper_bound没有等于），返回值是地址，如果要转换成下标，减去首地址即可：

查找默认是升序序列，如果要在降序序列里查找，需要在查找规则里写上greater<int>()。

方案执行

为得到最长上升子序列，假设一个数组d，同时用top记录数组的末元素。

1. 如果a[i] > d[top]，那么就把a[i]加到d的末端，更新top，这样，保证d是一条单调上升的序列。
   （此时top代表着a[i]结尾的最长升序列的长度）
2. 如果a[i] <= d[top]，那么就用lower_bound在d中找到小于等于a[i]的元素下标p，用a[i]替换掉d[p]。
   （此时p代表这a[i]结尾的最长升序列的长度）

为什么成立？

1. 在我们用a[i]更新的时，无论是哪种情况，我们都保证d前面的数组的元素排在a[i]前面。
2. 每次遇到第二种情况时，我们都是选择用现有的元素将原有元素进行替代，而不是插入，这样保证了最长序列的长度是不变的，同时降低原有元素的值，优化了序列的质量：本来就能放后面的值，还是能，本来放不了的值，现在降低了门槛，能替代，这样，最后降低了末尾元素的值，就可以使序列保证整体最长，元素最小

由于替代操作改变了a数组元素的位置，因此，i前面的元素并不是按照a顺序排列的，是按照大小排列的，d数组的元素d[i]代表的不是以d[i]结尾的序列是d[1……i]，而是代表着当a[j]更新到d[i]后，以a[j]结尾的序列的lis是i。

理论先写到这里，依然是导弹拦截为例题，代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int great[1010];
int les[1010];
int main() {
	ios::sync_with_stdio(false);
	int t , top1 = 0 , top2 = 0;
	cin >> t;
	great[++top1] = t;
	les[++top2] = t;
	while(cin >> t) {
		if( t > great[top1] )
			great[++top1] = t;
		else {
			int p = lower_bound(great+1 , great+top1+1 , t) - great;
			great[p] = t;
		}
		if( t <= les[top2] )
			les[++top2] = t;
		else {
			int p = upper_bound(les+1 , les+top2+1, t,greater<int>()) - les;
			les[p] = t;
		}
	}
	cout << top2 << " " << top1;
}