最长串那点事儿pascal
（最长上升子序列，最长公共子串，最长公共子序列，最长公共上升子序列）的优化与另类状态表示思路
DP中很经典的一类，又分这几小类
1. 最长（不）上升/下降
2. 最长公共子序列/串
3. 最长公共上升子序列
算法复杂度，一般就是朴素的n^2或n^3，其实很多优化，最朴素的不再叙述：
一：NlongN 最长不降系列
F是维护一个单调的序列，f[i]不为0的元素中的最大的i（即队列长度）
Program sky;
Var
i,j,m,n:longint;
function find(l,r:longint):longint;{ 从f中二分查找第一个大/小于(等于)a[i]的数覆盖}
begin
if l=r then exit(l);
if f[mid]…a[i] then exit(find(l,mid)) else exit(find(mid+1,r));
end;
begin
for i:=1 to n do
if a[i]>f[tot] then begin inc(tot); f[tot]:=a[i]; end
else f[find(1,tot)]:=a[I,j];
end.
二：最长公共子串
用01矩阵可以直观表示某一位是否匹配，改变存储方式，让矩阵中的每一位转移它左上角元素的状态
If a[i]=b[j] then F[I,j]:=f[i-1,j-1]+1;否则为0，朴素二维循环
三：最长公共上升子序列
（1）朴素n^3（f[i,j]表示状态，意思是到a的前i位，b的前j位的最长值，当更新f时用第三维枚举）
program sky;
begin
readln(n); for i:=1 to n do read(a[i]);{ 第一个序列}
readln(m); for i:=1 to m do read(b[i]);{ 第二个序列}
for i:=1 to n do
for j:=1 to m do
begin
if a[i]<>b[j] then f[i,j]:=f[i-1,j] else{ 分情况，当不等时不会更新ans，所以直接转移下来供下面用}
begin
f[i,j]:=1;
for k:=0 to j-1 do if a[i]>b[k] then f[i,j]:=max(f[i,j],f[i-1,k]+1);
end;
end;
for i:=1 to m do f[n,m]:=max(f[n,m],f[n,i]);{ 最优解不一定在最后，还有一种写法就是f[i,j]转移f[i-1,j],f[i,j-1]的最大值}
writeln(f[n,m]);
end.
（2）优化至n^2（用k记录位置，压缩维度的两种方法之一，【另一种是改变状态表示】）
for i:=1 to n do
begin
maxa:=0;
for j:=1 to m do{ 和n^3的不同，因为它会判断f[j]>maxa这一状态转移，所以不能f[j]:=max(f[j],f[j-1])，也就是不能把左边的状态转移过来}
begin{ 空间上也采用压缩，这行状态之和前一行有关，所以直接覆盖}
if (a[i]>b[j]) and (f[j]>maxa) then maxa:=f[j];{ 注意if语句中的else，用else的话，if就不能随便嵌套了···}
if (a[i]=b[j]) then f[j]:=max(f[j],maxa+1);
end;
end;
for i:=1 to m do f[m]:=max(f[m],f[i]);
writeln(f[m]);
四：特殊最长公共子序列的nlogn算法（若两序列都没有重复元素，且元素不过大，把两序列各看做一个集合时，两集合相等，这时用一种新的状态表示方法）
这种新的状态表示方法就是记录第二个串中元素
（1）1D/1D
利用答案f数组的单调性，即后面的状态一定大于等于或小于等于前面的，ans成一个单调变化如下
111111111111111111111111111111111111111111111111111
111111111111222222222222222222222222222222222222222
111111111111222222222222222222222233333333333333333
不可能出现
111111111111111111111113333333333333333333322222222
这时存储答案的就不是f的值而是下标了，值表示左右端点
F[k].l与f[k].r分别表示ans为k的区间左右端点
代码和nlogn的最长上升完全一样，思想变了，变成找一个已经确定的位置被覆盖的最大值，并用它的位置更新可以覆盖它的最大的一个数的下一个数
（2）一个新的定义状态的方法，代码不变，不写了。
（3）根据题目性质转化成熟悉的问题
可以把元素在第二个序列中的位置按照第一个序列的顺序记录下来，求最长上升
Ep：2 1 3 4 5
1 3 2 4 5
V： 3 1 2 4 5
对v求一次最长上升用nlogn可以求解