Dyd's Blog

He who has a strong enough why can bear almost any how.

CF1584F Strange LCS

Posted on In
Symbols count in article: 2.4k Reading time ≈ 2 mins.

CF来到2600

Strange LCS

题意

$T \le 5$ 组数据，给定 $n \le 10$ 个字符串，字符集为大、小写字母且每个字符在同一个串中最多出现两次，求它们的LCS（最长公共子串）

做题

暴力做法就类似两个串的LCS，直接 $10$ 维dp，时间……

发现有信息没用：字符集为大、小写字母且每个字符在同一个串中最多出现两次

先考虑如果每个字符只出现一次怎么办，由于字符集不大，可以考虑设计状态为 d[ch] 表示“以**字符 $ch$ **结尾的前缀子串的LCS”，方程明显为 $d[i] = \max(d[j]) + 1$ ，这里要保证在所有串中字符 $j$ 都在字符 $i$ 的前面，关于字符的位置可以预处理

现在，字符出现了两次，当然可以延续上面的做法，预处理字符的位置，把状态设计为“以字符 $ch$ 结尾的前缀子串的LCS”，但同时我们必须知道这个字符在每个串中是第几次出现，考虑状压，用一个二进制数 $s$ 表示在每个串中是第几次出现，则状态 d[ch][s] 表示“以字符 $ch$ 在第 $i$ 个串中第 $k_i$ 次出现结尾的前缀子串的LCS”，其中 $k_i$ 是 $s$ 中压缩的信息， $k_i = 0 / 1$ 表示第 $1 / 2$ 次出现

转移的时候有个贪心：可以从 $k_i = 1$ 转移就不必从 $k_i = 0$ 转移，因为第 $2$ 次出现一定在第 $1$ 次后面，以它结尾的前缀子串一定包含了第 $1$ 次，所以转移时，设当前转移为 $d[ch][s] \gets d[j][t]$ ，直线枚举字符 $j$ ，若在串 $i$ 中字符 $ch$ 前有两个 $j$ 就从 $k_i = 1$ 转移，有一个就从 $k_i = 0$ 转移，换句话说，我们在枚举 $j$ 时就确定了 $t$

考虑时间，设字符集大小为 $V$ 状态有 $V \times 2^n$ 个，每次转移要枚举字符 $j$ 并 $O(n)$ 得到 $t$ ，故时间为 $O(V \times 2^n \times V \times n) = O(V^2 2^n n)$

由于判断较多，具体实现可以考虑记忆化搜索

代码

稍微压了压行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 10 + 5, NN = (1 << 10) + 5, V = 52 + 5, INF = 0x3f3f3f3f;
int n, pos[N][V][2], d[V][NN], fr1[V][NN], fr2[V][NN]; //fr记录来向
int dp(int ch, int s)
{
    if (d[ch][s] != -1) return d[ch][s];
    int mx = 0;
    for (int i = 0, j, t; i < V; ++i)
    {
        for (j = 1, t = 0; j <= n; ++j)
            if (pos[j][i][0] >= pos[j][ch][(s >> (j - 1)) & 1]) break;
            else if (pos[j][i][1] < pos[j][ch][(s >> (j - 1)) & 1]) t |= 1 << (j - 1);
        if (j > n && dp(i, t) >= mx) mx = d[i][t] + 1, fr1[ch][s] = i, fr2[ch][s] = t;
    }
    return d[ch][s] = mx;
}
void out(int id1, int id2)
{
    if (fr1[id1][id2] != -1) out(fr1[id1][id2], fr2[id1][id2]);
    if (id1 < 26) printf("%c", id1 + 'a');
    else printf("%c", id1 + 'A' - 26);
}
int main()
{
    int T, mx, mxid1, mxid2;
    STC char s[V << 1];
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        mx = 0, mxid1 = mxid2 = -1;
        //这里要是极大
        memset(pos, 0x3f, sizeof pos), memset(d, -1, sizeof d), memset(fr1, -1, sizeof fr1);
        for (int i = 1, j, len; i <= n; ++i)
            for (scanf("%s", s + 1), j = 1, len = strlen(s + 1); j <= len; ++j)
            {
                if (s[j] >= 'a' && s[j] <= 'z') s[j] -= 'a';
                else s[j] += 26 - 'A';
                if (pos[i][s[j]][0] >= INF) pos[i][s[j]][0] = j;
                else pos[i][s[j]][1] = j;
            }
        for (int i = 0, j, t; i < V; ++i)
        {
            for (j = 1, t = 0; j <= n; ++j)
                if (pos[j][i][0] >= INF) break;
                else if (pos[j][i][1] < INF) t |= 1 << (j - 1);
            if (j > n && dp(i, t) >= mx) mx = d[i][t] + 1, mxid1 = i, mxid2 = t;
        }
        printf("%d\n", mx);
        if (mxid1 != -1) out(mxid1, mxid2);
        puts("");
    }
    return 0;
}