题目描述

给定 $n$ 个字符串，每个字符为大写或小写字母，求 $n$ 个串的最长公共子序列。

每个字符在每个字符串中出现次数不多于 $2$。

$n\leq 10$。

思路

设 $f_{i,S}$ 表示公共字符串最后一个字符为 $i$，且对于 $n$ 个串，匹配的字符是前面的 $i$ 还是后面的 $i$ 的状态为 $S$。

转移就是找到一个字符 $j$ 接在 $i$ 后面，转移顺序由 $i$ 在 $s_1$ 中的位置决定。

时间复杂度 $O(Tn|{\scriptsize \sum}|^22^n)$

代码

#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

string s[12];
int p[100][100][2], f[100][1 << 12];
pair<int, int> la[100][1 << 12];

void dfs(int x, int y) {
    if (x == 52) return;
    dfs(la[x][y].first, la[x][y].second);
    if (x < 26) putchar('a' + x);
    else putchar('A' + x - 26);
}

int id(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    return c - 'A' + 26; 
}

void solve() {
    int n;
    scanf("%d", &n);
    memset(p, -1, sizeof p);
    vector<int> tn(n + 5);
    for (int i = 1; i <= n; i ++ ) {
        cin >> s[i];
        tn[i] = (int)s[i].size();
        for (int j = 0; j < tn[i]; j ++ )
            if (p[i][id(s[i][j])][0] == -1) p[i][id(s[i][j])][0] = j;
            else p[i][id(s[i][j])][1] = j;
    }
    memset(f, 0xc0, sizeof f);
    f[52][0] = 0;
    for (int i = 0; i <= tn[1]; i ++ ) {
        for (int st = 0; st < (1 << n); st ++ ) {
            for (int j = 0; j < 52; j ++ ) {
                int flg = 1, y = 0;
                for (int k = 1; k <= n; k ++ ) {
                    int x = -1;
                    if (i > 0) x = p[k][id(s[1][i - 1])][st >> k - 1 & 1];
                    if (p[k][j][0] > x) {
                        ;
                    } else if (p[k][j][1] > x) {
                        y |= 1 << k - 1;
                    } else {
                        flg = 0;
                    }
                }
                if (flg) {
                    if (f[i > 0 ? (id(s[1][i - 1])) : 52][st] + 1 > f[j][y]) {
                        f[j][y] = f[i > 0 ? (id(s[1][i - 1])) : 52][st] + 1;
                        la[j][y] = {i > 0 ? (id(s[1][i - 1])) : 52, st};
                    }
                }
            }
        }
    }
    int ans = 0, tx = 52, ty = 0;
    for (int i = 0; i < 52; i ++ )
        for (int j = 0; j < (1 << n); j ++ )
            if (f[i][j] > ans) {
                ans = f[i][j];
                tx = i, ty = j;
            }
    printf("%d\n", ans);
    dfs(tx, ty);
    putchar('\n');
}

int main() {
    int T;
    scanf("%d", &T);
    while (T -- ) {
        solve();
    } 
    return 0;
}