仙人长曰：我精通打牌
\(\quad\qquad\quad f_i\)表示第 \(i\) 个元素结尾的 \(\rm LIS\) 长度，则 \(f_i=max(f_i,f_j+1),j< i~\&\&~a_j< a_i\) 。枚举 \(i,j\) 即可。
for(int i=1;i<=n;++i){
for(int j=1;j<i;++j){
if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
}
}
\(\quad\qquad\quad\)考虑用数据结构优化方法 \((1)\)，由于是依次插入序列中的元素，所以当前时刻数据结构中所有的值都是 \(i\) 及之前的元素。那么我们只需要查找 \([1,a_i-1]\) 的 \(f_{max}\) 来更新答案，即我们只需要一个支持单点修改和维护前缀区间最大值的数据结构。线段树是一个很好的选择。
for(int i=1;i<=n;++i){
f[i]=query(1,1,n,1,a[i]-1)+1;
update(1,1,n,a[i],f[i]);
}
\(\quad\qquad\quad\)先把做法摆出来：维护一个单调栈，对于每次新添加的元素 \(a_i\) ，如果 \(a_i>stk_{top}\) ，就直接把 \(a_i\) 丢到栈里去；否则从栈中 \(lower\)_\(bound\) 出第一个大于等于 \(a_i\) 的数，把它用 \(a_i\) 替换掉。
\(\quad\qquad\quad\)这个做法乍一看很玄学，证明如下：
\(\quad\qquad\quad\)设 \(f_i\) 表示以权值 \(i\) 结尾的答案数量， \(g_i\) 表示 \(f_{[1,i-1]}\) 的最大值，\(\Delta g\) 为 \(g_i\) 的差分数组。那么显然 \(f_i=g_i+1\) 。我们每次插入 \(a_i\) ，那么 \(f_{a_i}\) 更新为 \(g_{a_i}+1\) 。然后考虑这样对于后面的 \(g\) 的影响。由于这个元素是后插入的，所以一定不影响到之前插入的元素的答案 \(f\) ，同时 \(g\) 也一定只改变某一段空的区间。
\(\quad\qquad\quad\)举个栗子： \(1,4,2,4,5,6\)
\(\quad\qquad\quad\)先插入 \(1\)
| 数组 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| \(f\) | 1 | 0 | 0 | 0 | 0 | 0 |
| \(g\) | 0 | 1 | 1 | 1 | 1 | 1 |
| \(\Delta g\) | 0 | 1 | 0 | 0 | 0 | 0 |
\(\quad\qquad\quad\)再插入 \(4\)
| 数组 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| \(f\) | 1 | 0 | 0 | 2 | 0 | 0 |
| \(g\) | 0 | 1 | 1 | 1 | 2 | 2 |
| \(\Delta g\) | 0 | 1 | 0 | 0 | 1 | 0 |
\(\quad\qquad\quad\)再插入 \(2\)
| 数组 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| \(f\) | 1 | 2 | 0 | 2 | 0 | 0 |
| \(g\) | 0 | 1 | 2 | 2 | 2 | 2 |
| \(\Delta g\) | 0 | 1 | 1 | 0 | 0 | 0 |
\(\quad\qquad\quad\)剩下的自己手膜一下吧。
\(\quad\qquad\quad\)从栗子中我们可以看出，每次我们修改 \(g\) 的时候，只需要从 \(a_i+1\) ，到 \(a_i+1\) 往后及 \(a_i+1\) 本身这样一个范围中，第一个非零的数（设为 \(pos\) ）之前的所有 \(g\) 值都 \(+1\) ，也就相当于在 \(\Delta g\) 上 \(\Delta g_i++,\Delta g_{pos}--\)。
\(\quad\qquad\quad\)回到做法中，我们维护一个单调栈相当于存储了所有有权值的 \(f\) ，然后每次是在 \(a_i\) ~ \(a_{pos}\) 进行修改，将 \(f_{a_i}\) 赋予权值然后 \(f_{pos}\) 的答案就可以忽略不计了（因为我们实际上维护的是 \(\Delta g\) ，而 \(a_{pos}\) 对 \(\Delta g\) 的贡献已经被 \(a_i\) 给覆盖掉了）。最后我们的答案，其实就是 \(\Delta g\) 的和，也就是栈的长度。（因为每一次如果是入栈操作则 \(len++\) ，\(\Delta g\) 的和也 \(++\)；如果是替换操作则 \(len\) 不变， \(\Delta g\) 的和先 \(+1\) 再 \(-1\) 也不变）
d[1]=a[1];
for(int i=2;i<=n;++i){
if(d[len]<a[i])d[++len]=a[i];
else *lower_bound(d+1,d+1+len,a[i])=a[i];
}
\(\quad\qquad\quad\)这个应该只能用方法 \((2)\) 来做，只需要记录一下从哪里转移过来的即可。
\(\quad\qquad\quad\)考虑 \(dp\) 。
\(\quad\qquad\quad\)我们可以发现，如果两个序列一个是升序，另外一个乱序时，求两个序列的 \(\rm LCS\)其实就是在求乱序序列的 \(\rm LIS\) （因为有一个序列是升序的，所以一定存在乱序序列的最长上升子序列与升序序列的序列有最长公共子序列）。
\(\quad\qquad\quad\)所以我们在一开始输入 \(a\) 序列的时候就将它序列中的元素逐一编号，然后再在 \(b\) 序列给对应的元素编上在 \(a\) 序列中的编号，也就是 \(b\) 序列中元素在 \(a\) 序列中的位置。
\(\quad\qquad\quad\)比如说
a: 1 5 4 3 2
b: 5 3 1 2 4
\(\quad\qquad\quad\)编号之后就是
a: 1 2 3 4 5
b: 2 4 1 5 3
\(\quad\qquad\quad\)然后对 \(b\) 求 \(\rm LIS\) 即可。
\(\quad\qquad\quad\)但是需要注意的是：
\(\quad\qquad\quad\)首先，序列元素不可重。因为如果重复的话，你标完好以后的 \(a\) 数组不能保证升序。比如说 \(1,2,1,3,3\) ，实际上标完好以后的序列是 \(0,2,1,0,5\) ，某些位置被覆盖掉了。
\(\quad\qquad\quad\)其次，如果两个序列有不同元素，处理时要除去不同元素。显然除去不会对答案造成影响，不除去的话会出错（自己手膜几组样例就知道了）
\(\quad\qquad\quad\)设 \(f_{i,j}\) 表示 \(a_1\) ~ \(a_i\) 和 \(b_1\) ~ \(b_j\) 并以 \(b_j\) 结尾的最长公共上升子序列。
\(\quad\qquad\quad\)这样做的复杂度是 \(\mathcal O(n^3)\) 的。
\(\quad\qquad\quad\)但是我们可以通过维护 \(k\) 来实现优化。
\(\quad\qquad\quad\)先丢代码：
for(int i=1,k=0;i<=n;++i,k=0){
for(int j=1;j<=m;++j){
if(a[i]==b[j])f[i][j]=f[i-1][k]+1,pre[j]=k;//pre记录前一位，用于记录具体LCIS
else f[i][j]=f[i-1][j];
if(a[i]>b[j]&&f[i-1][j]>f[i-1][t])k=j;
}
}
\(\quad\qquad\quad\)前面两句好理解，关键是第三句。对于我们当前枚举到的 \(a_i\) ，我们要找的是一个满足 \(a_i=b_g\) 的 \(g\) ，然后再在 \(g\) 的基础上找一个 \(k\) 满足 \(b_k < b_g\) ，那么我们可以更换一下枚举的 \(g,k\) 顺序。显然，我们将要找到的 \(b_g=a_i\) ，然后再去找 \(b_k< b_g\) ，其实就等效于维护一个 \(b_k < a_i\) ，因为反正最后要找到的 \(b_g=a_i\) 。同时又要记录 \(f\) 最大，因此就是上面那个式子了。
\(\quad\qquad\quad\)若是要求具体 \(\rm LCIS\) 就记录一下 \(pre\) 就可以了。
原文：https://www.cnblogs.com/Zikual/p/13251926.html