题目描述

难度分:$2600$

输入$T(\leq 5)$表示$T$组数据。

每组数据输入$n(2 \leq n \leq 10)$和$n$个字符串，只包含大写和小写英文字母，且对于每个字符串，每个字母最多出现两次。

计算这$n$个字符串的最长公共子序列（$LCS$）。输出$LCS$的长度和对应的任意$LCS$。

输入样例

4
2
ABC
CBA
2
bacab
defed
3
abcde
aBcDe
ace
2
codeforces
technocup

输出样例

1
A
0

3
ace
3
coc

算法

状压DP

周五一般都是学习的一天，这个状态定义确实是第一次见。

先考虑更简单的问题如果每个字母只出现一次，那么对于两个字母$c_1$和$c_2$，它们必须在所有的字符串中都是相同的相对顺序（假设$c_1$都出现在$c_2$之前），才能保证$c_1$可以转移到$c_2$。这就给了我们一个DP的顺序，对于第一个字符串$s_0$，从中选择两个字母$s_{0,i}$和$s_{0,j}$，满足$i \lt j$，只要所有其他字符串中都满足这个相对顺序，就可以进行状态转移$f[j]=max(f[j],f[i]+1)$，其中$f[i]$表示字符串$s_0$的子串$[0,i]$与其他字符串的最长公共子序列长度。

状态定义

但是本题的每个字母最多出现两次，所以还需要一维状态，记为$f[i][mask]$。$mask$表示匹配到每个字符串的$s_{0,i}$的位置，$mask$的第$i$位为$0$表示$s_{0,i}$在第$i$个串中处于第一次出现的位置，$mask$的第$i$位为$1$表示$s_{0,i}$在第$i$个串中处于第二次出现的位置。

状态转移

因此，我们转移时直接在$s_{0}$上枚举下一个匹配的位置$j$，找到最小的$mask$（这里是一个贪心的思想，尽量让匹配到的字母靠前，这样能够让后面有更多余地匹配其他字符）。还需要后一个字母在所有串中的出现位置不会在前一个字母在所有串中的出现位置前面，实现的时候细节比较多，还要记录每个状态的转移来源，这样才能通过回溯获得一个具体方案，详见代码。

复杂度分析

时间复杂度

枚举$i$时第一个串是需要完整遍历的，对于每个$i$，需要枚举$2^n$个位置状态$S$，以及下一个匹配位置$j \gt i$。最内层对于每个$i$、$S$、$j$，还需要检查是不是$i$和$j$的相对位置在每个字符串中都合法，又是$O(n)$的遍历。因此，整个算法时间复杂度为$O(n\Sigma^22^n)$，其中$\Sigma$表示字符集的大小，本题中包括所有的大小写字母，大小为$52$。

空间复杂度

空间瓶颈在于DP数组$f$，以及每个状态的转移来源数组$from$，它们的大小都是状态数量$2\Sigma \times 2^n$（两倍是因为每个字母最多出现两次，因此字符串长度上限就是$2\Sigma$）。因此，整个算法的额外空间复杂度为$O(\Sigma2^n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

#define mem(x, v, s) memset(x, v, sizeof(x[0])*s) 
const int N = 10, S = 110;

int T, n, ap, aS, len[N];
int f[S][1<<N], buc[N][S], p[N][S][2];
PII from[S][1<<N];
char s[N][S];

void print(int i, int S) {
    if(i == 0) return;
    print(from[i][S].first, from[i][S].second);
    putchar(s[0][i - 1]);
}

int main() {
    unordered_map<char, int> mp;
    for(char c = 'a'; c <= 'z'; c++) {
        mp[c] = c - 'a';
    }
    for(char c = 'A'; c <= 'Z'; c++) {
        mp[c] = 26 + (c - 'A');
    }
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        mem(f, 0, S);
        mem(buc, 0, N);
        ap = aS = 0;
        for(int i = 0; i < n; i++) {
            scanf("%s", s[i]);
            len[i] = strlen(s[i]);
            for(int j = 0; j < len[i]; j++) {
                int id = mp[s[i][j]];
                // p[i][id][buc[i][id]]表示字母id在s[i]中出现状态为buc[i][id]时是哪个索引位置
                p[i][id][buc[i][id]++] = j;
            }
        } 
        for(int i = 0; i < len[0]; i++) {
            for(int S = 0; S < 1<<n; S++) {
                if(i == 0 || f[i][S]) {
                    // 枚举下一个字符j
                    for(int j = i + 1; j <= len[0]; j++) {
                        bool ok = true;
                        int mask = 0;
                        int pr = i > 0? mp[s[0][i - 1]]: 0;
                        int su = mp[s[0][j - 1]];
                        for(int sid = 0; sid < n && ok; sid++) {
                            int b = S>>sid&1;
                            if(buc[sid][su] == 0 || i > 0 && buc[sid][pr] <= b) {
                                ok = false;
                                break;
                            }
                            if(i == 0) continue;
                            int pos = p[sid][pr][b], fd = -1;
                            for(int k = 0; k < buc[sid][su] && fd == -1; k++) {
                                if(p[sid][su][k] > pos) fd = k;
                            }
                            fd == -1? ok = false: mask |= fd<<sid;
                        } 
                        int v = i == 0?1 : f[i][S] + 1;
                        if(ok && f[j][mask] < v) {
                            f[j][mask] = v;
                            from[j][mask] = {i, S};
                            if(v > f[ap][aS]) {
                                // 贪心，优先选前面的j
                                ap = j;
                                aS = mask;
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n", f[ap][aS]);
        print(ap, aS);
        puts("");
    }
    return 0;
}