LIS 问题:
设 \(f[i]\)为以 \(a[i]\)结尾的最长上升子序列长度, 有:
\[f[i]=f[j]+1(j<i&&a[j]<a[i])\]
可以用树状数组优化至 \(O(nlogn)\)
基于排列的 LCS 问题 (\(a,b\) 均为排列, 即一个元素不会出现多次):
设 \(pos_i\)为 \(a_i\)在 \(b\)中出现的位置, 即 \(a_i=b_pos_i\).
\(a\)的一个子序列 \(a_p_1,a_p_2,...,a_p_m\)是 \(a,b\)的公共子序列等价于 \(pos_p_1<pos_p_2<...<pos_p_m\)
求一个 LIS 即可.
一般 LCS 问题:
经典解法:
设 \(f[i][j]\)表示只考虑 \(a\)中前 \(i\)个,\(b\)中前 \(j\)个的最长公共子序列长度, 有:
\[f[i][j]=\left\{ \begin{aligned} & f[i-1][j-1] & a[i]=b[j]\& max(f[i-1][j],f[i][j-1]) & a[i]!=b[j]\\end{aligned} \right.\]
十分简单, 但是还有一种稍微复杂但是拓展性更高的做法:
设 $f[i][j]$ 表示只考虑 $a$ 中前 $i$ 个,$b$ 中前 $j$ 个并且 $b_j$ 已经和 $a_1,...,a_i$ 中的某一个匹配的最长公共子序列长度, 有:
\[f[i][j]=\left\{ \begin{aligned} & f[i-1][j] & a[i]!=b[j]\& max(f[i-1][k]+1) & a[i]==b[j],k<j\\end{aligned} \right.\]
为什么说这样拓展性更好? 来看这样一道题 http://www.joyoi.cn/problem/codevs-2185
题目要求最长上升公共子序列, 不能直接用 LCS 的经典解法了, 但是我们仔细思考一下, 发现如果我们用上面的转移方程, 我们只需要在从 \(f[i-1][k]\)转移到 \(f[i][j]\)时, 只需要保证 \(b[k]<b[j]\)即可, 所以我们得到新的转移方程:
\[f[i][j]=\left\{ \begin{aligned} & f[i-1][j] & a[i]!=b[j]\& max(f[i-1][k]+1) & a[i]==b[j],k<j&&b[k]<b[j]\\end{aligned} \right.\]
又因为当 \(a[i]==b[j]\)时,\(b[k]<b[j]\)等价于 \(b[k]<a[i]\), 在转移枚举 \(j\)时对所有 \(b[k]<a[i]\)的 \(f[i-1][k]\)记录一个前缀 \(max\)即可.
代码:
- #include<bits/stdc++.h>
- using namespace std;
- #define N 5007
- int f[N],a[N],b[N];
- int main()
- {
- int i,j,n;
- scanf("%d",&n);
- for(i=1;i<=n;i++)
- scanf("%d",&a[i]);
- for(i=1;i<=n;i++)
- scanf("%d",&b[i]);
- int maxx=0,ans=0;
- for(i=1;i<=n;i++)
- {
- maxx=0;
- for(j=1;j<=n;j++)
- {
- if(b[j]==a[i])f[j]=max(f[j],maxx+1);
- else if(b[j]<a[i])maxx=max(maxx,f[j]);
- ans=max(ans,f[j]);
- }
- }
- printf("%d\n",ans);
- return 0;
- }
当然还有对于一般 LCS 问题的 \(O(nlogn)\)解法(不严格), 同样可以拓展至此题, 先留坑吧.
来源: http://www.bubuko.com/infodetail-3150201.html