CF1584F Strange LCS

· · 题解

CF1584F. Strange LCS *2600

仍然是从简化版入手。考虑弱化版 “每个字符只出现一次” 怎么做：对于两个字符 x,y，如果它们在第一个字符中的出现位置 p_x,p_y 有 p_x>p_y，那么 x 不可能转移到 y。这给予我们 DP 的顺序：枚举从 1 到 l_1 的所有位置 i,j\ (1\leq i< j\leq l_1)，若 s_{1,i} 在每个字符串的出现位置都在 s_{1,j} 之前，那么 i 可以转移到 j，\mathrm{checkmax}(f_j,f_i+1)，其中 f_i 表示 s_{1,1\sim i} 与其他所有字符串的 LCS 长度最大值。

不难将其扩展到本题的做法：只需要再记录一个 mask S，f_{i,S} 表示匹配到每个字符串 s_{1,i} 的前一个出现位置还是后一个出现位置。转移时枚举下一个字符 j 求出 最小的 mask（这里用了贪心的思想，能靠前尽量靠前显然更优）即可。时间复杂度 \mathcal{O}(Tn|\Sigma|^22^n)，代码写起来还是很舒服的。

#include <bits/stdc++.h>
using namespace std;

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

int T, n, ap, aS, len[N], mp[1 << N];
int f[S][1 << N], buc[N][S], p[N][S][2];
pii tr[S][1 << N];
char s[N][S];
void print(int i, int S) {
    if(!i) return;
    print(tr[i][S].first, tr[i][S].second), putchar(s[0][i - 1]);
}
int main(){
    for(int i = 0; i < 26; i++) mp['a' + i] = i;
    for(int i = 0; i < 26; i++) mp['A' + i] = i + 26;
    cin >> T;
    while(T--) {
        cin >> n, mem(f, 0, S), mem(buc, 0, N), ap = aS = 0;
        for(int i = 0; i < n; i++) {
            cin >> 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]++] = j;
            }
        } for(int i = 0; i < len[0]; i++)
            for(int S = 0; S < 1 << n; S++) if(!i || f[i][S])
                for(int j = i + 1; j <= len[0]; j++) {
                    int ok = 1, msk = 0, pr = i ? mp[s[0][i - 1]] : 0, su = mp[s[0][j - 1]];
                    for(int q = 0; q < n && ok; q++) {
                        int b = S >> q & 1;
                        if(!buc[q][su] || i && buc[q][pr] <= b) {ok = 0; break;}
                        if(!i) continue;
                        int cp = p[q][pr][b], fd = -1;
                        for(int k = 0; k < buc[q][su] && fd == -1; k++)
                            if(p[q][su][k] > cp) fd = k;
                        fd == -1 ? ok = 0 : msk |= fd << q;
                    } int v = !i ? 1 : f[i][S] + 1;
                    if(ok && f[j][msk] < v) {
                        f[j][msk] = v, tr[j][msk] = {i, S};
                        if(v > f[ap][aS]) ap = j, aS = msk;
                    }
                } cout << f[ap][aS] << "\n", print(ap, aS), puts("");
    }
    return 0;
}