894A题解|894A Solution

发表于 更新于 Waline： 阅读次数： 本文字数： 992 阅读时长 ≈ 1 分钟

这是之前出的一道题，稍微进行了一些小修改。
题目链接:https://codeforces.com/contest/894/problem/A

  1. 最简单的方法就是搜索遍历所有的可能的排列情况，即枚举结果字符串的每一位在原字符串中的位置，故复杂度为$O(n^3)$，如果需要的匹配的字符串更长，那么复杂度更高。

  2. 随后可以发现目标字符串要完全符合要求，意即只要有一位不符合就一定不被计算，故可剪枝，只有当前面的字符串都符合要求的时候才继续遍历，常数可以进行优化为原来的$\frac{1}{26}$，但复杂度仍旧不变。

  3. 从前面的剪枝可以发现并不一定要遍历每种可能才可以，可以保存中间量直接相加即动态规划。

可以一维存储原字符串的下标，一维存目标字符串的下标，表示到目前为止符合的字符串数量，随后从前往后相加得最后得数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for (int j = 0; j < 105; j++)
{
    for (int i = 1; i < 5; i++)
    {
        dp[i][j] = 0;
    }
    dp[0][j]=1;
}
for (int j = 0; j < st.length(); j++)
{
    for (int i = 0; i < 3; i++)
    {
        if (st[j] == base[i])
        {
            dp[i + 1][j + 1] = dp[i][j] + dp[i+1][j];
        }
        else
        {
            dp[i + 1][j + 1] = dp[i + 1][j];
        }
    }

最后输出dp[3][st.length()]作为答案。

可以注意到过程当中一直是dp[i]到dp[i+1]，说明实际并不需要这一维度，可以删去这一维度到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (int i = 1; i < 5; i++)
{
    dp[i] = 0;
}
dp[0] = 1;
for (int j = 0; j < st.length(); j++)
{
    for (int i = 0; i < 3; i++)
    {
        if (st[j] == base[i])
        {
            dp[i + 1] = dp[i] + dp[i + 1];
        }
        else
        {
            dp[i + 1] = dp[i + 1];
        }
    }
}

同时注意到else实际上什么都没有做，可以直接删去。