CF1303E. Erase Subsequences

发表于 | 阅读数

询问能否从$S$中找到不重复的两个子序列$t1+t2=T$。$|S|,|T|\leq 400$

考虑$n^3$的算法，枚举$t1,t2$的分界线。

设$dp[i][j]$，匹配到$t1,i$长度,匹配到$t2,j$长度。此时到$S$的长度。

$dp[i+1][j]=min(d[i+1][j],pos[dp[i][j]][t1[i+1]])$。

$dp[i][j+1]=min(d[i][j+1],pos[dp[i][j]][t1[j+1]])$。

$pos[i][j]$表示$i$后面下一个$j$的位置。

  • 显然$dp[i][j]$越小越好，$dp[i][j]$一定是按照某种顺序转移过来，所以不存在$t1,t2$选到重复。
代码 
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 4e3 + 10;
const int mod = 1e9 + 7;

int dp[N][N];
int ch[N][26];
char s[N], t[N];
int slen, tlen;
void init()
{
    for (int i = 0; i < 26; i++)
        ch[slen][i] = 0;
    for (int i = slen; i >= 1; i--)
    {
        for (int j = 0; j < 26; j++)
            ch[i - 1][j] = ch[i][j];
        ch[i - 1][s[i] - 'a'] = i;
    }
}
bool check(int x)
{
    int len1 = x;
    int len2 = tlen - x;
    for (int i = 0; i <= len1 + 1; i++)
        for (int j = 0; j <= len2 + 1; j++)
            dp[i][j] = slen + 100;
    dp[0][0] = 0;
    for (int i = 0; i <= len1; i++)
        for (int j = 0; j <= len2; j++)
        {
            //cout << i << " " << j << "---" << endl;
            //cout << ch[dp[i][j]][t[i + 1] -'a' ] << endl;
            if (ch[dp[i][j]][t[i + 1] - 'a'] != 0)
                dp[i + 1][j] = min(dp[i + 1][j], ch[dp[i][j]][t[i + 1] - 'a']);
            if (ch[dp[i][j]][t[j + 1 + len1] - 'a'] != 0)
                dp[i][j + 1] = min(dp[i][j + 1], ch[dp[i][j]][t[j + 1 + len1] - 'a']);
        }
    //cout << len1 << " " << len2 << endl;
    //cout << dp[3][2] << endl;
    if (dp[len1][len2] <= slen)
        return 1;
    return 0;
}
int T;
int main()
{
    scanf("%d", &T);
    while (T--)
    {

        int flag = 0;
        scanf("%s", s + 1);
        scanf("%s", t + 1);
        slen = strlen(s + 1);
        tlen = strlen(t + 1);
        memset(ch, 0, sizeof(ch));
        init();
        // cout << check(3) << endl;
        // cout << ch[0]['a' - 'a'] << endl;
        for (int i = 1; i <= tlen; i++)
        {
            if (check(i))
            {
                //cout << i << endl;
                flag = 1;
                break;
            }
        }
        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
}