题目链接：https://contest.ucup.ac/contest/1699/problem/8521

题目大意：略。

做法

很有意思的 dp ，如果一开始想对了方向就会很简单，但是一旦一开始想错了方向，就会花很多时间了。

fl[i][j]/fr[i][j] 表示的是从 Si 左边往右边/右边往左边匹配 T 的从 j 开始的前缀/后缀能匹配都多少，如果能完整匹配就记录所需的最短长度。

转移是显然的，记录答案的时候需要注意，由于 fl,fr 只能记录 S 前缀或者后缀的最小值，而如果我们想要知道 S 内部的答案，就需要枚举。

注意到若答案在 Si 内部，我们先把 Si 用 Si−1,Si−2 表示，答案要么还在里面，要么横跨两个串，即不断下去，答案一定可以跨过：SiSj(|i−j|≤1) ，或者答案的长度为 1 。

但问题来了，我们要枚举 i 到什么地步为止？

我们设 t 表示最小的 t 满足 St≥3n （不难证明，不会有连续三个 a ，连续两个 b，所以当 St≥3n 时，T 一定是其子序列）

因此如果把字符串表示成 St,St+1 的组合，答案一定不会跨过三个字符串，所以 i≤t+1 就行了。

时间复杂度：O(nlog⁡n) 。

cpp
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);
}
// left to right
// right to left
int dp[L][2][N];//>=0 num <0 len
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;
    }
    /*
    只要第一次满足匹配的 t >= 3 就可以在下面求出答案，所以对 t=0,1,2 特判。
    */
    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. 1…. 后面一定是 b。

  2. 不会有aaa…. ，与下面同理，1… 的结构在两次 aa 后一定会生成

  3. 不会有连续三个 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 的形式。

而这种结构两次一定会生成成功。

  1. 不会有连续三个 ab ，同样的逻辑，当 01 生成时，接下来一定是：aa，同理一定会生成。

  2. 综上，任何一个前缀在两次经过后一定会生成。

  3. 一定不会有连续两个 ab ，逻辑：研究 babab 的结构，发现一开始必须是 001 ，矛盾。

感觉这个 dp 非常的有意思，用 dp 来完成了匹配，感觉以前没有见过。

和官方做法基本一致，在此不再赘述。