当前位置：网站首页>L3-2 至多删三个字符 (30 分)

L3-2 至多删三个字符 (30 分)

2022-08-09 20:51:00 【Here_SDUT】

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

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

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

输入样例：

ababcc

输出样例：

25

提示：

删掉 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”。

分析： 记 dp[i][j] 表示考虑前i个字符，删j个的方案数，那么对于第i个字符，有两种可能：删或者不删，对应的状态转移方程为：

  • 删：dp[i][j] += dp[i-1][j-1]
  • 不删： dp[i][j] += dp[i-1][j]

然而现实没有那么美好，这样可能会出现重复的字符串，如：xxxxbdbxxxx（x表示任意字符），我们发现删去“bd”或者“db”的结果都相同，即剩下一个b，这里就产生的重复。

也就是说，如果有一段字符串前后字母相同，记长度为 k ，且 k\leq j+1，那么就会产生重复。为什么是j+1？因为最多只能删 j 个字符，所以要想将这一段字符删得只剩下头和尾，那么长度必须小于等于 j+1 。那么有多少个这样的字符重复了呢？

由于为了使得首尾相同的字符串删得只剩下头或者尾，已经消耗掉了 k-1次删除, 所以还剩下 j – k +1 次可以删去，对应的数量就是 dp[p-1][j-k+1]，其中这里的p指的是这段收尾相同的字符串的首字母的下标。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
LL dp[maxn][5];
char s[maxn];
int main(int argc, char const *argv[]) {
    cin >> s+1;
    int n = strlen(s+1);
    dp[0][0] = 1;//初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 3; j++) {
            if (i < j) break;//没法删，直接跳过
            dp[i][j] += dp[i - 1][j];// 不删i
            if (j) dp[i][j] += dp[i - 1][j - 1];//删i
            for (int k = i - 1; k >= 1 && j >= i - k; k--) {//找i之前是否有和i相同的
                if (s[i] == s[k]) {//去重
                    dp[i][j] -= dp[k - 1][j - (i - k)];
                    break;
                }
            }
        }
    }
    LL ans = 0;
    for (int i = 0; i <= 3; i++) ans += dp[n][i];//累加起来
    cout << ans;
    return 0;
}
原网站

版权声明
本文为[Here_SDUT]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2069184

边栏推荐

猜你喜欢

随机推荐