AcWing 1017. 怪盗基德的滑翔翼

显然是求从一个点开始的最长下降子序列，但是更为显然的是从两边分别出发做两次最长下降子序列，
这样中间的所有点都可能作为途径点或者出发点，答案一定为最大。

code

AcWing 1014. 登山

题目指定只能从1走到n，中途不能反向，且一旦有下山操作就不能再上山，因此可以考虑
以第i座山作为登上的最高山，以两边分别做一遍$LIS$，得到i向左的最长下降和向右的最长下降即可

code

AcWing 482. 合唱队形
本题同上一题，依然以i作为最高点，两边为起点分别做$LIS$求得i向左和向右的最长
这样遍历后求得最大，则需要出队的同学数将达到最少。

code

AcWing 1012. 友好城市
可以知道的是当两个城市$x_1, x_2$连向对岸的城市$y_1, y_2$的大小与其相反
即$x_1 > x_2\ and\ y_1 < y_2$ 或 $x_1 < x_2\ and\ y_1 > y_2$
那么此时必然交叉，因此我们需要避免这种情况。

为了方便判断，先使得我们判定的左边城市是按坐标从小到大排好序的，
那么当所有左边连接的右边城市的坐标也是从小到大排序好的时，不会产生交叉。
因此先对左边城市按坐标排序，对右边城市做$LIS$即可。

code

AcWing 1016. 最大上升子序列和

考虑$f[i]$为以$i$为结尾的最大上升子序列和
那么转移为：$f[i] = max( f[j] \times (a[j] < a[i]) ) + a[i]$

code

AcWing 1010. 拦截导弹
我们将这个问题变换下，即问题1：求$LIS$长度，问题2：求最少可以将该序列分成几个上升子序列
问题1即是模板。
问题2即求解一下最长下降子序列。
这是因为：得到最长下降子序列的每个元素都将作为一个上升子序列的元素，且一个上升子序列只有一个元素会出现在我们所求的最长下降子序列中，否则就会出现非下降情况。

code

AcWing 187. 导弹防御系统
这里借用的$LIS$中的$dp$思想，$f[i]$表示以$i$为为结尾的最长上升子序列的长度。
那么这里的元素既可能为上升子序列的长度，也可能为下降子序列的长度，
因此我们枚举当前元素分别作为最长上升子序列和最长下降子序列的元素即可。

$up[k]$表示第$k$个上升子序列的末尾元素，$down[k]$表示第$k$个下降子序列的末尾元素，
当该元素比他们都大或逗笑，或者当前无上升子序列或下降子序列时，就可以新开一个上升/下降子序列

这里可以添加一个最优性剪枝，即当此时的状态必不可能更新答案，就没必要继续搜了。

code

AcWing 272. 最长公共上升子序列
$f[i][j]$的状态表示：
1. 集合： 所有以$A$串的前$i$个元素，$B$串的前$j$个元素，并且以$B[j]$为结尾的$LCIS$
2. 属性： 所有$LCIS$的最大长度

状态分解：
1. 不含$A[i]： f[i - 1][j]$
2. 包含$A[i]$： 则必然是$A[i]==B[j]$，
则转移前$B[j]$必然未被用过：$max(f[i - 1][k]) + 1, k < j \ and\ B[k] < B[j]$

时间复杂度：$O(n^3)$

考虑优化：
我们可以发现，对于当前枚举的$A[i]$，如果有$A[i]==B[j]$
因此枚举$B[k] < B[j]$时，相当于枚举$B[k] < A[i]$

再回忆下我们更新时的操作，每次取的是：
在$B[k] < A[i]$条件下，用$max(f[i - 1][k]) + 1$来更新$f[i][j]$
由于我们每次$j$是变大的，因此对于$f[i][j+1]$和$f[i][j]$，两者都需要用$f[i-1][k] + 1$来更新$f[i][j/(j+1)]$
因此只需要对这部分进行一个动态记录更新即可，此时时间复杂度降为：$O(n^2)$

code