CF1584F Strange LCS

给你 \(n\) 个由大小写字母构成的字符串，求它们的最长公共子序列。输出长度及字符串（任意一个）。

• \(n\le 10\)
• 在每个字符串中，每个字符至多出现 2 次

【Intuition】

一个字符串为最长公共子序列：

如果我们现在的对象是 t1 那么就可以通过 t2 来转移。

所以可以 dp。设一个表示分别从 s1,s2,…,sn 的 p1,p2,…,pn 位置起头（s1[p1]=s2[p2]=…=sn[pn]）能够跳的 LCS。

【Solution】

由于各串每个字符至多出现 2 次，可以将它们依次标记为 0,1。如果少于 2 次就不用标全。

枚举 \(t\) 当前字符 \(i\)，用一个 bitmask \(j\) 表示 \(s_p(1\le p\le n)\) 各自选的是 \(i\) 的几号位置。

设 \(f_{i,j}\) 表示上述情况下，从各自的位置开始的 LCS（长度）。用 (string) \(g_{i,j}\) 顺带记录字符串。

枚举 \(i\) 后面的 \(t\) 的字符 \(k\)。显然有 \(f_{i,j}=\max (1+f_{k,N[i][j][k]})\)。其中 \(N[i][j][k]\) 表示对于每个状态 \((i,j)\) 中的位置，往后找第一个 \(k\) 出现的位置，这些位置的号码构成的新状态 \((k,N[i][j][k])\)。

注意边界；预处理 \(N[i][j][k]\)。

时间复杂度 \(O(52\cdot 2^n\cdot 52\cdot n)\)。后面的 \(\cdot n\) 为预处理中产生，可以通过枚举子集省去，但不省去也可通过，如下；空间复杂度 \(O(52\cdot 2^n\cdot 52)\)。

【Submission】