对最长公共子序列(LCS)等一系列DP问题的研究
LIS问题:
设\(f[i]\)为以\(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\)个的最长公共子序列长度,有:
\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$中的某一个匹配的最长公共子序列长度,有:
\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.\]
为什么说这样拓展性更好?来看这样一道题
题目要求最长上升公共子序列,不能直接用LCS的经典解法了,但是我们仔细思考一下,发现如果我们用上面的转移方程,我们只需要在从\(f[i-1][k]\)转移到\(f[i][j]\)时,只需要保证\(b[k]<b[j]\)即可,所以我们得到新的转移方程:
\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)\)解法(不严格),同样可以拓展至此题。
在排列中,\(a\)中的每一个元素唯一对应\(b\)中的一个元素,但在一般的LCS问题中不是这样,一个元素可以对应多个元素。
怎么办呢?我们把\(a\)中每个元素在\(b\)中对应位置的集合拿出来,比如\(a={3,3,2,4},b={2,3,3,5}\),那么\(a\)中元素\(3\)对应的位置集合就是{2,3},将每个元素对应位置降序排列,再放回原序列中,对得到的新序列做一个LIS,就是最长公共子序列的长度,比如上面那个例子,a中每个元素对应集合为\(\{2,3\},\{2,3\},\{1\},\{\}\),得到的新序列就是\(3,2,3,2,1\),它的最长上升子序列是\(2,3\),即\(a,b\)的最长公共子序列是由\(b_2,b_3\)组成的,这时再套用LIS的\(O(nlogn)\)做法即可,但是这样复杂度不是严格\(O(nlogn)\)的,因为每个\(a\)中的元素最多对应\(n\)个b中的元素,最坏复杂度达到\(O(n^2 log n)\)。
至于这种做法到上面这题的拓展,因为你要保证你在\(a\)中选择的元素在\(b\)中的位置是递增的,同时要保证这些元素的值本身也是递增的,也就是这样:
\]
发现是转移一个二维偏序关系,二维数点即可,复杂度是不严格的\(O(nlog^2 n)\)。
最新文章
- 用 GitHub 来部署静态网页 ꒰・◡・๑꒱
- HTML5表单与PHP交互
- Nginx+Tomcat动静态资源分离
- webrtc学习——mediaStream和MediaStreamTrack
- JavaScript设计模式之工厂模式
- canvas绘图基础及基于粒子系统的雪花飘落
- ruby:借助第三方类名如何查找第三方gem名称(zlib为例)
- SpringBoot Web Https 配置
- HDU 2665 Kth number(主席树静态区间第K大)题解
- python中remove的一些坑
- 【python】单下划线与双下划线的区别
- Kubernetes学习之路(六)之创建K8S应用
- pre 强制换行
- CF 272E Dima and Horses 染色,dfs 难度:2
- icmp隧道手工操作
- HTML5——前端预处理技术(Less、Sass、CoffeeScript)
- C#文本框中默认是不允许使用全选的
- 《从零开始学Swift》学习笔记(Day 22)——闭包那些事儿!
- 解决:Eclipse安装Pydev插件报错: An error occurred while collecting items to be installed session context was:(profile=...
- 数据库导入sql文件