清北学堂模拟赛d5t5 exLCS

分析：比较巧妙的一道题.经典的LCS算法复杂度是O(nm)的，理论上没有比这个复杂度更低的算法，除非题目有一些限制.这道题中两个字符串的长度不一样，f[i][j]如果表示第一个串前i个，第二个串前j个的最长公共子序列的话，复杂度会爆.但是LCS的长度很小，能不能换一种状态的表示方法呢？

回想0/1背包问题的变形，如果体积特别大，价值特别小，我们可以把价值定义在状态里面，设f[i][j]表示前i个物品中价值为j的最小体积，最后扫一遍j看看符不符合条件就可以了，对于这道题我们可以也可以沿用这样的思路，把LCS的长度放到状态里面，设f[i][j]表示str1的前i个，LCS的长度为j的已经匹配到的str2的最左下标，先预处理一下当前位置的字母的下一次出现的位置，然后就可以递推了.

当dp题中状态很大，答案很小的时候可以把答案定义到状态中，最后扫一下看看是否满足要求就可以了.这种方法有点像二分一样:我知道了答案，检验答案是否可行.

代码中求nextt数组的做法值得学习！

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = , inf = 0x7ffffff;

int f[maxn][maxn], nextt[][], n, m, ans;

char a[], b[];

int main()

{

    scanf("%s%s", a, b);

    n = strlen(a);

    m = strlen(b);

    for (int i = ; i <= n; i++)

        for (int j = ; j <= n; j++)

            f[i][j] = inf;

    for (int i = ; i < ; i++)

        nextt[m][i] = inf;

    for (int i = m - ; i >= ; i--)

    {

        memcpy(nextt[i], nextt[i + ], sizeof(nextt[i]));

        nextt[i][b[i] - 'a'] = i;

    }

    f[][] = nextt[][a[] - 'a'];

    for (int i = ; i <= n; i++)

        f[i][] = -;

    for (int i = ; i < n - ; i++)

        for (int j = ; j <= n && f[i][j] < inf; j++)

        {

            f[i + ][j] = min(f[i + ][j], f[i][j]);

            if (j < n)

                f[i + ][j + ] = min(f[i + ][j + ], nextt[f[i][j] + ][a[i + ] - 'a']);

        }

    for (int i = n; i >= ; i--)

        if (f[n - ][i] != inf)

        {

            ans = i;

            break;

        }

    printf("%d\n", ans);

    return ;

}

巴特西

清北学堂模拟赛d5t5 exLCS

最新文章

热门文章