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

发布时间:2019年03月23日 阅读:292 次

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

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

输入格式:

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

输出格式:

在一行中输出至多删掉其中 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"。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<vector>
using namespace std;
#define ll long long int
#define INF 0x3f3f3f3f
#define Irish_Moonshine main
const int maxn = 1e6 + 10;
char str[maxn];
ll dp[maxn][4];
int Irish_Moonshine()
{
    scanf("%s", str);
    int len = strlen(str);
    for (int i = 0; i <= len; i++) dp[i][0] = 1;
    dp[0][1] = 1;
    for (int i = 1; i < len; i++) {
        dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
        if (str[i] == str[i - 1]) dp[i][1]--;

    }
    dp[1][2] = 1;
    for (int i = 2; i < len; i++) {
        dp[i][2] = dp[i - 1][1] + dp[i - 1][2];
        if (str[i] == str[i - 1]) dp[i][2] -= dp[i - 2][1];
        else if (str[i] == str[i - 2]) dp[i][2]--;
    }
    dp[2][3] = 1;
    for (int i = 3; i < len; i++) {
        dp[i][3] = dp[i - 1][3] + dp[i - 1][2];
        if (str[i] == str[i - 1]) dp[i][3] -= dp[i - 2][2];
        else if (str[i] == str[i - 2]) dp[i][3] -= dp[i - 3][1];
        else if (str[i] == str[i - 3]) dp[i][3]--;
    }
    ll ans = dp[len - 1][0] + dp[len - 1][1] + dp[len - 1][2] + dp[len - 1][3];
    printf("%lld\n", ans);
    return 0;
}
//_CRT_SECURE_NO_WARNINGS


Tag:
相关文章

发表评论: