我永远喜欢39号同学2018。
xh39
·
·
题解
前言
如果有看不懂，或者题解中有错误，欢迎指出。
本篇题解讲得比较详细，可能比较啰嗦，如果想看更简单了请移步其它题解或跳读。
前置算法
请先学习 状态压缩 dp
建议学习动态规划（dp）求最长公共子序列。会 O(n^3) 的做法即可。（其实这题我也没做）
题目大意
求 n 个字符串的最长公共子序列。
数据范围：n\le10，每个字符在同一个字符串中最多出现 2 次。只会出现 52 个英文大小写字母。大小写敏感。
注：
- 为方便状态压缩，除特殊说明外，以下所有编号从 0 开始。
- 为避免下标、括号过多造成困扰，有些数组用中括号代替下标。a[x] 表示 a_x。
- 所有 "之后" 都不包含当前。比如 3 之后 指 4,5,6,\ldots 而不包含 3。
-
- 字母表大小指出现的字符种类数。比如对于本题，只会出现 52 种字符，则字母表大小为 52。
经管理员反馈，暴力做法有些多余。所以放到这里，供有需要的看。
简化题目：每个字符在同一个字符串中最多出现 1 次。
只出现 1 次，让我们想到了用元素来表示下标。
设 f[i] 表示所有字符串都删掉字符 i 之后的字符，剩下的字符串的最长公共子序列。。其中 i 可以为字母表内任意字母，此处为 'a'~'z' 和 'A'~'Z'。
则 f[i]=max\{f[j]\}+1（j 在所有的字符串都出现在 i 位置的前面）
如果看了之前暴力的解法，这个状态转移方程也是同样的思路。故不多解释。
原题正解
每个字符在同一个字符串中最多出现 2 次。
还是采用同样的思路：用元素表示下标。
但是元素有重复了，怎么办？方法是记录第几次出现。
设 f[i][j_0][j_1][j_2]\ldots[j_{n-1}] 表示对于 s_k，删掉第 j_k 次出现的 i 之后的所有字符。其中 i 取英文字母，j 取 0 或 1。
状态转移方程：f[i][j_0][j_1][j_2]\ldots[j_{n-1}]=max\{f[c][d_0][d_1][d_2]\ldots[d_{n-1}]\}+1 (d 要满足 s_k 中，字符 c 在第 d_k 次出现在 字符 i 第 j_k 次 前面）
但是这怎么转移呢，难道枚举 d？这样是可以的，因为 n\le10。时间复杂度为 O(52\times 4^n) 但是不优，代码也比较难写。考虑继续优化。
继续优化
采用贪心的策略。对于 s_k，如果有 d_k=1 的转移，则 d_k=0 一定不比 d_k=1 优。
因为第 0 次出现一定比第 1 次前面。删除第 1 次后面的情况包含了删除 0 次之后的情况。因为在第 0 次与第 1 次之间的字符可以不选。
所以在转移的时候枚举完 c 就可以计算出 d。看 s_k 出现当前位置（字符 i 第 j_k 次出现的位置）之前有多少个 c 字符。如果有 2 个则 d_k=1，有 1 个则 d_k=0，如果没有说明这个字符 c 不合法，无法进行状态转移。
时间复杂度：共 2^n 个状态，转移需要枚举第一维的字符，并需要 O(n) 求出 d 数组实现后面许多维的转移，所以是这两个乘起来，看代码就很快能分析复杂度。所以在本题中，复杂度(字母表大小 52 的常数不省略)为 O(52\times n\times 2^n)。
如果将本题拓展一下，每个字符在同一个字符串中最多出现 ci 次。且字母表大小为 bet。此时 d 数组的取值就为 0~(ci-1) 那么复杂度为 O(bet\times n\times ci^n)。
具体实现
$j=0或1$，这让我们想到了**状态压缩**。具体地，**用一个 $n$ 位二进制数表示 $n$ 个状态**。设这个数为 $g$，则 $g=2^0\times j_0+2^1\times j_1+2^2\times j_2+\ldots+2^{n-1}\times j_{n-1}$。可以发现，每一个 $g$ 表示了唯一的 $j$。
那么 $f[i][g]=max\{f[c][h]\}+1$。（$h$ 可以通过 继续优化 板块中的方法先计算 $d$ 数组，然后计算得出，$c$ 为任意合法的字符）
---
输出方案：每个状态都**记录它是从哪个状态转移过来的**。
具体地，可以记录字符 $x(i,g)$ 和整数 $y(i,g)$ 表示 $f[x(i,g)][y(i,g)]$ 是最大值。（$f[i][g]=max\{f[c][h]\}+1$ 中找出最大的 $f[c][h]$，然后，$x(i,g)=c,y(i,g)=h$）
具体见代码。
---
由于 $i$ 是字符，转移不方便。所以将字符对应成数字。代码中 'a'~'z' 对应 0~25；'A'~'Z' 对应 26~51。
---
统计答案与转移类似。如果一个字符在 $s_k$ 中出现了 $2$ 次，则 $d_k=1$，$1$ 次则 $d_k=0$，$0$ 次则不合法。
## 代码
由于还是有很多无用状态，并且不方便按调用的先后顺序递推，于是用记忆化递归实现。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int m[25],f[105][10005],tkr0[105][10005],tkr1[105][10005],id[2][25][105],n,ykb;
//m:字符串长度。ykb:pow(2,n)。
//id[0][i][j]:第i个串中第0次出现类型j的字符的位置。id[1][i][j]:第1次。
//shu[i][j][k]:第i个串第j个位置前有几个类型k的字符。
//tkr0,tkr1分别表示题解中讲到的 x(i,g) 和 y(i,g)。
string s[25];
int fyr(int zifu,int ci,int step){ //zifu:最后一个公共字符。ci:出现几次的集合,就是题目中的g。这个就表示了 f[i][g]。step是调试的时候用的，请忽略。
if(f[zifu][ci]>=0){
return f[zifu][ci];
}
int i,j,Max=0,maxid=-1,s_; //s_表示通过d数组计算出的g。实际上并不需要把d数组存下来,可以依次求其每一位,同时更新s_的值。具体见下。
for(i=0;i<52;i++){ //枚举转移的字符。
s_=0;
for(j=0;j<n;j++){ //依次判断每个字符串。
if(id[0][j][i]>=id[(bool)(ci&(1<<j))][j][zifu]){ //如果之前没有出现过这个字符。
break;
}
if(id[1][j][i]<id[(bool)(ci&(1<<j))][j][zifu]){ //如果出现过2次。此时d_k=1,否则d_k=0。
s_|=(1<<j); //将第j位修改为1。由于初始时s_=0，所以未修改的位默认为0。
}
}
if(j==n&&fyr(i,s_,step+1)>=Max){ //前一个for循环正常结束时j应该等于n。如果j!=n则说明提前break了，说明有一个字符串之前没出现过此字符。
Max=f[i][s_]+1;
tkr0[zifu][ci]=i; //存下从哪里转移过来的。
tkr1[zifu][ci]=s_;
}
}
f[zifu][ci]=Max;
return Max;
}
void out(int aaa,int bbb){ //输出方案部分。
if(tkr0[aaa][bbb]>=0){ //如果等于-1说明没有前一个状态了。就是以这个状态为开头(即此时f=1)。
out(tkr0[aaa][bbb],tkr1[aaa][bbb]);
}
if(aaa<26){ //用递归模拟栈输出aaa。
cout<<(char)(aaa+'a');
}else{
cout<<(char)(aaa-26+'A');
}
}
void Main(){
cin>>n;
ykb=(1<<n);
memset(id,39,sizeof(id));
memset(f,-1,sizeof(f));
memset(tkr0,-1,sizeof(tkr0));
int i,j,Max=0,maxid0=-1,maxid1=-1,s_;
for(i=0;i<n;i++){
cin>>s[i];
m[i]=s[i].size();
for(j=0;j<m[i];j++){
if(islower(s[i][j])){ //将字符转化为数字。
s[i][j]=s[i][j]-'a';
}else{
s[i][j]=s[i][j]-'A'+26;
}
if(id[0][i][s[i][j]]>12345){ //如果>12345，说明是没有被存储过的,此时是第0次出现，否则是第1次出现。
id[0][i][s[i][j]]=j;
}else{
id[1][i][s[i][j]]=j;
}
}
}
//统计答案部分。与转移类似,不详细解释。
for(i=0;i<52;i++){
s_=0;
for(j=0;j<n;j++){ //依次判断每个字符串。
if(id[0][j][i]>12345){ //如果没有出现过这个字符。
break;
}
if(id[1][j][i]<12345){ //如果可以选第 1 个。
s_|=(1<<j);
}
}
if(j==n&&fyr(i,s_,0)>=Max){
Max=f[i][s_]+1;
maxid0=i;
maxid1=s_;
}
}
cout<<Max<<endl;
if(maxid0!=-1){ //maxid0==-1说明没找到比0大的，即Max=0。
out(maxid0,maxid1);
}
cout<<endl;
}
int main(){
int t,i;
cin>>t;
for(i=0;i<t;i++){
Main();
}
return 0;
}
```
## 题外话
分享一下(赛时/赛后)做这题的心路历程和代码中的一些细节。
40分钟做完 ABC，然后看 D，思考许久，还是感觉不可做。看 E，感觉可做，但就是一直想不出来。直到看完F,才发现 F 比 D,E 要简单许多。大概一眼就能想到大概的解法。但是对于今年提高组 24 分连三等奖都没拿到的我，在剩下不到一小时的时间内做完是不可能的。最后在 18:00 左右的时候才调出来。
所以下次比赛还是应该看完所有题目再挑最容易的做。（如果一眼想到正解可以马上开始写）
一开始，在求 $d$ 数组那一部分我没想到贪心转移的细节，然后就想用类似轮廓线的方法转移。后面发现贪心就可以了。
然后，一年多没 AC 过状态压缩，所以写出了一堆错误。这里只举三个典型一点的错误：
```id[(bool)(ci&(1<<j))][j][zifu]``` 这里我一开始没加 ```(bool)```，就是把位运算看成了逻辑运算，然后就数组越界了，调了很久。
然后，我认为只需要输出字符即可，所以记录方案时只记录了代码中的 tkr0,然后发现根本无法转移，所以卡了一会儿。
接着，统计答案部分我也写错了，就认为对于原问题 $d$ 数组所有元素都为 $1$(相当于 $g=2^n-1$)，调用时直接写 ```if(j==n&&fyr(i,ykb-1,0)>=Max){``` 。后面才发现 **不一定所有字符都出现了 $2$ 次。所以统计答案时也要求 $d$ 数组。**