L3-2 Delete up to three characters (30 points)

Given a string consisting of all lowercase English letters, allowing you to delete up to 3 characters, how many different strings are possible as a result?

Input format: Enter a string consisting of all lowercase English letters in one line and the length is in the interval [4, 10^6].

Output format: Output the number of different strings in one line with at most 3 characters removed.

Sample input:

ababcc

Sample output:

25

Tip:

Delete 0 characters to get "ababcc".

Remove 1 character to get "babcc", "aabcc", "abbcc", "abacc" and "ababc".

Remove 2 characters to get "abcc", "bbcc", "bacc", "babc", "aacc", "aabc", "abbc", "abac" and "abab".

Delete 3 characters to get "abc", "bcc", "acc", "bbc", "bac", "bab", "aac", "aab", "abb" and "aba".

Analysis: Remember that dp[i][j] means consider the first i characters and delete the number of j programs, then forThere are two possibilities for the i-th character: delete or not delete, and the corresponding state transition equation is:

• Delete: dp[i][j] += dp[i-1][j-1]
• Do not delete: dp[i][j] += dp[i-1][j]

However, the reality is not so good, so there may be repeated strings, such as: xxxxbdbxxxx (x represents any character), we found that deleting "bd" or "db" results in the same, that is, leaving a b,Here comes the repetition.

That is to say, if there is a string with the same letters before and after, and the length is k and k\leq j+1, then repetition will occur.Why j+1?Since only j characters can be deleted at most, if you want to delete this section of characters to only the head and tail, the length must be less than or equal to j+1 .So how many of these characters are repeated?

Since k-1 deletions have been consumed in order to delete only the head or tail of strings with the same head and tail, there are still j – k +1span> times can be deleted, and the corresponding number is dp[p-1][j-k+1], where p here refers to the subscript of the first letter of the string with the same ending.

Code:

#include #define LL long longusing namespace std;const int maxn = 1e6 + 10;const int inf = 0x3f3f3f3f;const double PI = acos(-1.0);typedef pair 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;//Initializationfor (int i = 1; i <= n; i++) {for (int j = 0; j <= 3; j++) {if (i < j) break;//Cannot delete, skip directlydp[i][j] += dp[i - 1][j];// do not delete iif (j) dp[i][j] += dp[i - 1][j - 1];//delete ifor (int k = i - 1; k >= 1 && j >= i - k; k--) {//Find i before whether there is the same as iif (s[i] == s[k]) {//Removedp[i][j] -= dp[k - 1][j - (i - k)];break;}}}}LL ans = 0;for (int i = 0; i <= 3; i++) ans += dp[n][i];//accumulatecout << ans;return 0;}