很有意思的 dp ，如果一开始想对了方向就会很简单，但是一旦一开始想错了方向，就会花很多时间了。
$fl[i][j]/fr[i][j]$ 表示的是从 $S_{i}$ 左边往右边/右边往左边匹配 $T$ 的从 $j$ 开始的前缀/后缀能匹配都多少，如果能完整匹配就记录所需的最短长度。
转移是显然的，记录答案的时候需要注意，由于 $fl,fr$ 只能记录 $S$ 前缀或者后缀的最小值，而如果我们想要知道 $S$ 内部的答案，就需要枚举。
注意到若答案在 $S_i$ 内部，我们先把 $S_i$ 用 $S_{i-1},S_{i-2}$ 表示，答案要么还在里面，要么横跨两个串，即不断下去，答案一定可以跨过：$S_{i}S_{j}(|i-j|\le 1)$ ，或者答案的长度为 $1$ 。
但问题来了，我们要枚举 $i$ 到什么地步为止？
我们设 $t$ 表示最小的 $t$ 满足 $S_{t}\ge 3n$ （不难证明，不会有连续三个 $a$ ，连续两个 $b$，所以当 $S_{t}\ge 3n$ 时，$T$ 一定是其子序列）
因此如果把字符串表示成 $S_{t},S_{t+1}$ 的组合，答案一定不会跨过三个字符串，所以 $i\le t+1$ 就行了。
时间复杂度：$O(n\log{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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int L = 40;
const int N = 2e5 + 5;
void get_char_array(char *s){
static char ss[N];
cin >> ss;
memcpy(s + 1, ss, strlen(ss) + 1);
}
int dp[L][2][N];
char st[N];
int n, f[L];
int main(){
get_char_array(st);
n = strlen(st + 1);
if(n == 1){
cout << 1 << "\n";
return 0;
}
if(n == 2 && st[1] == 'a' && st[2] == 'b'){
cout << 2 << "\n";
return 0;
}
for(int i = 1; i <= n; i++){
if(st[i] == 'a') dp[1][0][i] = dp[1][1][i] = 1;
else if(st[i] == 'b') dp[0][0][i] = dp[0][1][i] = 1;
}
for(int t = 0; t <= 1; t++){
for(int i = 1; i <= n; i++){
if(i + dp[t][0][i] == n + 1) dp[t][0][i] = -1;
if(i - dp[t][1][i] == 0) dp[t][1][i] = -1;
}
}
f[0] = f[1] = 1;
int ans = -1e9;
for(int t = 2; ; t++){
f[t] = f[t - 1] + f[t - 2];
for(int i = 1; i <= n; i++){
if(dp[t - 1][0][i] < 0) dp[t][0][i] = dp[t - 1][0][i];
else{
int j = i + dp[t - 1][0][i];
if(dp[t - 2][0][j] < 0) dp[t][0][i] = dp[t - 2][0][j] - f[t - 1];
else dp[t][0][i] = dp[t - 2][0][j] + dp[t - 1][0][i];
}
if(dp[t - 2][1][i] < 0) dp[t][1][i] = dp[t - 2][1][i];
else{
int j = i - dp[t - 2][1][i];
if(dp[t - 1][1][j] < 0) dp[t][1][i] = dp[t - 1][1][j] - f[t - 2];
else dp[t][1][i] = dp[t - 1][1][j] + dp[t - 2][1][i];
}
}
for(int i = 1; i < n; i++){
if(dp[t][1][i] < 0 && dp[t - 1][0][i + 1] < 0) ans = max(ans, dp[t][1][i] + dp[t - 1][0][i + 1]);
if(dp[t][1][i] < 0 && dp[t][0][i + 1] < 0) ans = max(ans, dp[t][1][i] + dp[t][0][i + 1]);
if(dp[t - 1][1][i] < 0 && dp[t][0][i + 1] < 0) ans = max(ans, dp[t - 1][1][i] + dp[t][0][i + 1]);
}
if(f[t - 1] >= n * 3){
assert(dp[t - 1][0][1] < 0);
break;
}
}
cout << -ans << "\n";
return 0;
}
|
当时想题时记录的一些性质
注意放 $a(0)$ 还是 $b(1)$ 可以用下面的方法生成：
初始有个全 $0$ 的串，每次在最左边放 $1$ ，然后没有相邻两个 $1$ ，就删掉向右边进 $1$ ，即每个 $1$ 分别表示：$1,2,3,5,…$ 。
然后第一个是 $0/1$ 代表了是放 $a$ 还是 $b$ 。
1…. 后面一定是 b。
不会有aaa…. ，与下面同理，1… 的结构在两次 aa 后一定会生成
不会有连续三个 aa ：
0100000000…. b
0010000000…. a
1010000000…. a
0001000000…. b
1001000000…. a
0101000000…. b
0000100000…. b
0000100000…. a
1000100000…. a
0100100000…. b
0010100000…. a
1010100000…. a
0000010000…. b
1000010000…. a
0100010000…. b
0101010000…. b
0000001000…. a
1000001000…. a
0100001000…. b
0010001000…. a
1010001000…. a
0001001000…. b
1000001000…. a
0100001000…. b
逻辑，当 001 这种结构生成的时候，接下来一定会是：abab 的形式。
而这种结构两次一定会生成成功。
不会有连续三个 ab ，同样的逻辑，当 01 生成时，接下来一定是：aa，同理一定会生成。
综上，任何一个前缀在两次经过后一定会生成。
一定不会有连续两个 ab ，逻辑：研究 babab 的结构，发现一开始必须是 001 ，矛盾。
感觉这个 $dp$ 非常的有意思，用 $dp$ 来完成了匹配，感觉以前没有见过。
和官方做法基本一致，在此不再赘述。
