[CF83E] Two Subsequences 题解
思路
定义 \(overlap(a, b)\) 为字符串 \(a\) 的后缀与 \(b\) 的前缀的最大相等的长度，有 \(|f(a, b)| = |a| + |b| - overlap(a, b)\)，下文称匹配为相邻两串的 \(overlap\)。
观察到每次操作之后，一定有一个序列是以 \(a_i\) 为结尾的。
所以根据这个性质设计状态：\(f_{i ,j}\) 表示考虑到 \(a_i\)，另一个序列以 \(a_j\) 结尾的最少长度。
但是这个状态设计并不好，因为没法进一步优化，发现 \(|a_i|\le 20\)，所以尝试把另一个序列的结尾状压进状态表示，另外为了方便，可以做一步转化（不做也可以）：最后序列的最短长度就等于总长度减去最多能匹配的长度。
所以可以列出这个状态表示：\(f_{i, s}\) 表示考虑到 \(a_i\)，另一个序列结尾为 \(s\) 的最大匹配数量。
推出状态转移方程为：（为了方便书写，这里省略和状态原值取 \(\max\) 的步骤）
\[\begin{aligned} f_{i, s}\gets f_{i - 1, s} + overlap(a_{i - 1}, a_i)\\ f_{i, a_{i - 1}}\gets f_{i - 1, s} + overlap(s, a_i) \end{aligned} \]-
第一个转移代表把 \(a_{i - 1}\) 和 \(a_{i}\) 放到同一个序列里面；
-
第二个转移代表 \(a_{i - 1}\) 和 \(a_i\) 不在同一个序列里面，这种情况下要枚举另一个序列结尾本来是什么来转移。
这样是 \(O(2^{|a|}n)\) 的，会超时，考虑优化：
首先发现第一个转移是对所有的 \(f_{i, s}\) 都加上一个值之后取 \(\max\)，因为是对所有状态的操作，所以每次加上的这个值可以使用一个标记 \(tag\) 维护。
那么瓶颈就到了第二个转移上面，发现第二个转移的特点是只有一个状态发生了改变，并且每次加上的值都介于 \(0\sim |a|\) 之间，非常小，考虑枚举加上的值，也就是上一个串 \(s\) 的后缀和 \(a_i\) 前缀匹配数。
这样就可以把第二个转移写成：
\[f_{i, a_{i - 1}} \gets \max_{k = 0}^{|a|}(\max_{s_{|a| - k + 1\sim |a|} = a_{i_{1\sim k}}} (f_{i - 1, s}) + k) \]进一步发现第二个 \(\max\) 可以预处理出来，具体而言，定义 \(g^i_{k, x}\) 表示 \(\max_{s_{|a| - k + 1\sim |a|} = x} (f_{i - 1, s})\)。
把 \(g\) 代入原式：
\[f_{i, a_{i - 1}} \gets \max_{k = 0}^{|a|}(g^i_{k, a_{i_{1\sim k}}} + k) \]这样如果得到了 \(g\) 数组，我们就可以实现对 \(f\) 的 \(O(|a|)\) 转移。
如何得到 \(g\) 呢，我们发现对于 \(g^i\) 而言它的大部分转移都和 \(g^{i - 1}\) 相似，只会相差 \(\Delta tag\)，而唯一一个会改变的是第二维为 \(a_{i - 1}\) 的状态，这个每次更新完 \(f\) 之后对 \(g\) 进行更新即可。
之后进行滚动数组优化即可通过此题。
实现
注意一些细节，所有的 \(f\) 状态是默认会加上 \(tag\) 的，所以转移的时候要减掉 \(\Delta tag\) 来转移。
时间复杂度：\(O(n|a|\sim n|a|^2)\)，这个波浪号取决于你怎么实现 \(overlap\)，时间允许当然暴力好写，追求极致可以写 Exkmp。
// Problem: Two Subsequences
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-12-06 22:07:10
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
string a[N];
int n, m, f[(1 << 20) + 5], g[22][(1 << 20) + 5], tag;
int overlap(string a, string b) {
for(int i = m; ~i; i --) {
bool flg = 1;
for(int j = 0; j < i && flg; j ++)
if(a[m - i + j] != b[j]) flg = 0;
if(flg) return i;
}
return 0;
}
int change(string x) {
int t = 0;
for(int i = 0; i < m; i ++)
t = t * 2 + (x[i] - '0');
return t;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
m = a[1].size();
memset(f, -0x3f, sizeof f), memset(g, -0x3f, sizeof g);
for(int i = 2, delta = 0; i <= n; i ++) {
delta = overlap(a[i - 1], a[i]);
int now = change(a[i - 1]);
tag += delta;
f[now] = max(-delta, f[now]); // 这个转移来自于那些本来第二个序列里面没有放东西的
for(int j = 0, t = 0; j <= m; j ++) {
f[now] = max(f[now], g[j][t] + j - delta);
if(j < m) t = t * 2 + (a[i][j] - '0');
}
for(int j = 0, t = 0; j <= m; j ++) {
g[j][t] = max(g[j][t], f[now]);
if(j < m) t += (1 << j) * (a[i - 1][m - j - 1] - '0');
}
}
int ans = tag;
for(int i = 0; i < (1 << m); i ++)
ans = max(ans, f[i] + tag);
cout << n * m - ans << '\n';
return 0;
}