L3-020 至多删三个字符

Statement

Metadata

作者: 曹鹏
单位: Google
代码长度限制: 16 KB
时间限制: 400 ms
内存限制: 64 MB

给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？

输入格式

输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, $10^6$ ] 内的字符串。

输出格式

在一行中输出至多删掉其中 3 个字符后不同字符串的个数。

输入样例

ababcc

输出样例

提示：

删掉 0 个字符得到 "ababcc"。

删掉 1 个字符得到 "babcc", "aabcc", "abbcc", "abacc" 和 "ababc"。

删掉 2 个字符得到 "abcc", "bbcc", "bacc", "babc", "aacc", "aabc", "abbc", "abac" 和 "abab"。

删掉 3 个字符得到 "abc", "bcc", "acc", "bbc", "bac", "bab", "aac", "aab", "abb" 和 "aba"。

Tutorial

思路：

$f[i][j]$ 表示到第 $i$ 个字符，已经删去了 $j$ 个字符的方案数。

有转移：

f[i][j] = f[i - 1][j] + f[i - 1][j - 1]

但是这样会有重复，我们考虑什么情况会重复。

比如说：aabab 中的 bab，我们删去 ba，得到 aab，删去 ab 得到 aab，两者是相同的

1 2 3 4 5
a a b a b

我们假设之前的每一位存的都是没有重复的方案数
就刚才的情况，我们发现当我们递推到第 $5$ 个位置的时候，删去第三位和第四位的ba，但是保留着第五位的b
那这种情况和递推到第 $3$ 个位置的时候，保留着第 $3$ 位的b是一样的

即：

\begin{eqnarray*} f[5][2] &=& f[2][0] \\ f[5][3] &=& f[2][1] \end{eqnarray*}

减去这些重复情况，我们就能保证已经递推过来的情况中没有重复情况。

简单来说，就是当前字符 $i$ ，该字符前一个出现的位置是 $j$ ，那么我们考虑删去 $i$ 这个字符，并且这时用了 $x$ 次删除次数，那么我们多花费 $i - j - 2$ 次的删除次数，将 $(i, j)$ 之间的字符全部删除，那么这种情况等价于删除 $j$ 那个字符，并且这是用了 $x$ 次删除次数的情况是相同的。

Solution

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n, pos[220];
ll f[N][4];
char s[N];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    memset(pos, -1, sizeof pos);
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        int d = pos[s[i]];
        pos[s[i]] = i;
        f[i][0] = f[i][1] = 1;
        for (int j = 1; j < 4; ++j) {
            f[i][j] += f[i - 1][j];
            f[i][j + 1] = f[i - 1][j];
            if (d != -1 && j - i + d >= 0)
                f[i][j] -= f[d - 1][j - (i - d)];
        }
    }
    printf("%lld\n", f[n][0] + f[n][1] + f[n][2] + f[n][3]);
    return 0;
}

Last update: May 4, 2022