2022ICPC网络赛 L LCS-like Problem（DP 子序列自动机）

265 0 0

作者:DM11

L LCS-like Problem（DP 子序列自动机）

题目：

给出两个串s, t。请找出一个最长的子序列(s')，使其与(t)的最长公共子序列长度不大于1。输出这个最长的长度。

思路：

题目名字是LCS，且题意比较符合DP的定义，优先考虑DP而非字符串来求解问题。

题目要求在s中找一个最长的满足题意的子序列。那么我们的状态表示一定是跟s有关的，又可以知道本题的转移一定是跟字符存在关系的。根据经验，可以定义出(f[i][j])表示在s的前i个字符中选择，且最后一个在t中出现的字符为j（这里是由后面转移时推出）的最大长度。

转移的时候，对于(s[i])的两种情况我们需要分别讨论。一：当(s[i])不在(t)中的时候，那么他可以跟在任何字符的后面。二：当(s[i])存在于(t)中的时候，我们要根据是否能接成一个长度大于1的子序列来判断是否能进行转移。

实现：

这里解答两个点，其一是对于f数组的定义。由于动态规划的无后效性，我们可以知道我们每次转移的时候只需要看最后一个字符就可以了。但是有一个问题，当最后一个字符(s[i])不在(t)的时候，如果定义为最后一个字符，就会覆盖掉上一个正在限制后面无效状态的状态。所以我们定义的是，最后一个在t中的字符。

其二是关于序列自动机这个东西。其实这个知识点还挺复杂的，详情可以观看下方链接。不过本题主要只是运用其思想，本题自动机状态非常简化，只需要保存字符(j)是否能在字符(i)的后面出现来辅助转移就可以完成。

https://blog.csdn.net/Berserker____/article/details/109062238

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
char s[N], t[N];
int n, m;
int vis[26]; //t中是否已经含有i
int ban[26][26]; //i的后面不能出现j 因为是子序列
int f[N][26]; //从s的前i个字符选出的子序列，且最后一个在t中出现的字符为j的最大长度

void init() //子序列自动机预处理
{
    for(int i = m; i >= 1; i --)
    {
        for(int j = 0; j < 26; j ++)
            if(vis[j])  ban[t[i]][j] = 1;
        vis[t[i]] = 1;
    }
}

int main()
{
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1);
    m = strlen(t + 1);

    for(int i = 1; i <= n; i ++)    s[i] -= 'a';
    for(int i = 1; i <= m; i ++)    t[i] -= 'a';

    init();

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j < 26; j ++)
            f[i][j] = f[i - 1][j] + (vis[s[i]] == 0); //如果s[i]没有在t中出现，可以直接接在后面，且不影响末尾
        for(int j = 0; j < 26; j ++)
            if(!ban[j][s[i]] && vis[s[i]]) //如果存在这个数，那么不能接在j的后面
                f[i][s[i]] = max(f[i][s[i]], f[i - 1][j] + 1);
    }

    int res = 0;
    for(int i = 0; i < 26; i ++)
        res = max(res, f[n][i]);
    cout << res << 'n';
}

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/DM11/p/16705945.html

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

2022ICPC网络赛 L LCS-like Problem（DP 子序列自动机）