最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤100000，
−109≤数列中的数≤109
输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

int a[N];//存题目数据的数组 
int q[N];//存每个数对应上升子序列的数组 

题解：q这个数组是一个记录“最小值”的数组，所谓的“最小值”就是——q[i]中每一个点都记录着某一个子序列个数的最小值。

就比如说这样一组数，q[1]=1，q[2]=2——因为最长子序列长度是1的那一位中‘1’是最小的一个,最长子序列长度是2的那一位中最小的那个数是‘2’。明确了q的概念再来分析性质。
‘4’和‘5’能接到3后面，那么其一定可以接到1后面，因为1比3小,可以为以后的序列留出更大的空间，此时2就可以插入其中，组成{1,2,4,5,6}这样一组最长上升子序列。
代码中的：q[r + 1] = a[i]：
我们可以用二分返回比当前q[i]小的数的下标r（如果当前的ai小于了q[当前]里的数，那么r返回的就是[当前]这个数的下标；此时把当前这个数的q[当前]直接更新成较小的那个数a[i]。如果当前的ai大于了q[当前]里的数，r返回的是当前这个数的下一个点的下标（向上取整）；那么你的q[当前+1]这个数就被赋值）
如果a[i]小于q[i]我们就更新q[i]让其等于a[i]，一直等到第一次出现一个a[i]比前面最小的那个q[i]大，那么我们可以给q[i+1]赋值为a[i]，经过一轮迭代，最终q[i+1]也将是比q[i]大且在所有q[i+1]中筛选出来的最小值。
如此更新我们发现q的图像一定是单调的,所以可以用二分更新q数组:

我们在二分返回r的同时更新长度len，最终len可以更新到的最大值就是我们根据性质推出的最长上升子序列的长度。

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;
int a[N];//存题目数据的数组 
int q[N];//存每个数对应上升子序列的数组 int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);int len = 0;for (int i = 0; i < n; i ++ ){int l = 0, r = len;while (l < r){int mid = l + r + 1 >> 1;if (q[mid] < a[i]) l = mid;else r = mid - 1;}len = max(len, r + 1);q[r + 1] = a[i];//更新q这个数组}printf("%d\n", len); return 0;
}

7-10 列车调度 (25 分)——天梯赛补题
火车站的列车调度铁轨的 结构如下图所示。
两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
输入格式：
输入第一行给出一个整数N (2 ≤ N ≤10^5)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例：

9
8 4 2 5 3 9 1 6 7

输出样例：

4

题解：本题难点就是如何抽象成一个最长上升子序列问题。

如果按照左边完全逆序入轨，我们至少需要9条铁轨。如果把4，5交换，那么5就可以和4一起站到一个铁轨上。那么只需要8条轨道。可以发现进入轨道之前的数如果都是递增的，那么就可以按照增序一个个出轨——即一条铁轨。那么这道题就可以看作一个求最长上升子序列的问题||导弹拦截问题||最多铁轨问题。
为什么导弹拦截和最长上升子序列是一致的呢？
同样q这个数组是一个记录“最小值”的数组。
按照上面的二分代码，如果飞来一系列递减的攻击导弹，防御导弹可以拦截比前一次高度低的攻击导弹么因为二分返回用来更新q数组的下标。

 if (q[mid] < a[i]) l = mid;else r = mid - 1;

而一段递减序列的最后一个元素——尾后缀被更新的时候必须打断这一段递减序列，此时我们的二分返回的就是q【下一个下标】（向上取整）——其意义就是最长子序列的个数增加一个||导弹拦截系统增加一套||铁轨条数增加一条。最后我们的q数组存的就是我们的最长上升子序列（上一题），其个数就是最长上升子序列个数，同样也是导弹拦截系统的个数，最少轨道条数。

代码同第一题。