LIS

即最长上升子序列
d(i)表示从从0到i的最长上升子序列,设a[n]=INF,最终答案为d(n)-1
$$d(i)=Max(1,d(j)+1 \,\,|\,\, i>j,a[i]>a[j])$$

$O(n^2)$ 算法

1
2
3
4
5
6
7
8
9
10
11
int LIS(int n)
{
a[n]=INF;
for(int i=0;i<=n;++i)
{
d[i]=1;
for(int j=1;j<i;++j)
if(a[i]>a[j]) d[i]=max(d[i],d[j]+1);
}
return d[n]-1;
}

$O(nlog{n})$ 算法

$g[k]$表示当前长度为k的序列的最后一个位置的最小值

显然 $g[1] \leq g[2] \leq g[3] \dots$

1
2
3
4
5
6
7
8
9
10
11
12
13
int LIS(int n) {
for(int i=1;i<=n;++i) g[i]=INF;
int res = 0;
for(int i=0;i<n;++i)
{
int k=lower_bound(g+1,g+n+1,a[i]) - g;
// 若为非严格递增,find中a[i]改为a[i]+1
d[i]=k;
g[k] = a[i];
ans = max(ans,k);
}
return res;
}

LCS

n个串的LCS是NPC问题,如无说明默认为两个串的LCS

$d(i,j)$表示序列a匹配到i,序列b匹配到j的LCS

$$
d(i,j)=\begin{cases}
d(i-1,j-1)+1 &a_i=b_j \\
Max(d(i-1,j),d(i,j-1)) &a_i \ne b_j
\end{cases}
$$

复杂度为$O(n^2)$

1
2
3
4
5
6
7
8
9
int LCS(int n,int m)
{
memset(d,0,sizeof d);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(a[i]==b[j]) d[i][j]=d[i-1][j-1]+1;
else d[i][j]=max(d[i-1][j],d[i][j-1]);
return d[n][m];
}

$O(nlogn)$算法

将LCS转化为LIS问题,应用$O(nlogn)$的LIS算法即可
假设两个序列 s1 = “abccba” 和 s2 = “acbdcab”
记录s1中每个元素在s2中出现的位置,然后降序排列

pos(a) = {5,0}
pos(b) = {6,2}
pos(c) = {4,1}

按照s1中字母的个数及pos数组排出对应的 s3 = {5,0,6,2,4,1,4,1,6,2,5,0}
最后对s3求LIS即为所求答案,LCS为所选数字对应字母序列。

p.s. 不过这种方法可能退化到$O(n^2logn^2)$

统计公共子序列个数

$d_{i,j} = d_{i-1,j} + d_{i,j-1} - d_{i-1,j-1} + (a_i = b_j?d_{i-1,j-1}+1:0)$

LCIS

最长公共递增序列
改进LIS算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int LCIS(int n,int m)
{
memset(f,0,sizeof(f));
for(int i=0;i<n;++i)
{
int k=0,p=-1;
for(int j=0;j<m;++j)
{
if(a[i]>b[j] && f[j] > k) k=f[p=j];
if(a[i]==b[j] && f[j] < k+1) f[j]=k+1,prev[j]=p;
}
}
int k=0,p=-1;
for(int i=0;i<m;++i) if(f[i]>k) k=f[p=i];

for(int i=k-1;i>=0;--i)
{
lcis[i]=b[p];
p=prev[p];
}

return k;
}

SCS

找到一个最短的字符串,其子序列包含了所有给定字符串

两个(不连续)

$|SCS|=|S1|+|S2|-|LCS|$

n个(连续)

poj1795

输出一个长度最短的字符串,包含所有给定子串,有多个答案则输出字典序最小的

集合dp
先把相互包含的串去掉,这样不会影响最终结果(不这样做反而无法dp)

然后建图,权值为前面串的后缀和后面串的后缀的公共长度。

$d_{i,S}$ 表示以第i个串开头,已选状态为S的重叠最大值

$d_{j,S|(1<<j)} = Max(d_{i,S} + G_{j,i}) \;\; ((S\&(1<<j)) == 0)$
最后答案为$ \sum |s_i| - Max(d_{i,(1<<n)-1})$

题目要求输出字典序最小的一个串,找出第一个位置递归打印即可
注意每次比较字典序大小是减去两串与前一个串的公共部分的,而不是直接比较两个串

回文子序列

最长

$$d(i,j)=
\begin{cases}
d_{i+1,j-1} + 2 &s[i]=s[j] \\
Max(d_{i+1,j},d_{i,j-1}) &s[i] \ne s[j]
\end{cases}
$$

统计

$$d_{i,j}=
\begin{cases}
d_{i+1,j} + d_{i,j-1} &s[i]=s[j] \\
d_{i+1,j} + d_{i,j-1} - d_{i+1,j-1} &s[i] \ne s[j]
\end{cases}
$$

msbop2015 Pre-B

不同子序列个数

考虑空串
$d[i] = 2d[i-1] - d[last[a[i]] - 1]$

cf-645e

长度为n的串,在后面添m个字符,使得其不同的子序列最多

我们考虑贪心地添加字符,即每次填的字符都是当前last最小的
因为$d[i]$是递增的,我们要保证越靠前其增速越快