题目描述
给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？
输入格式：
输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 10?6??] 内的字符串。
输出格式：
在一行中输出至多删掉其中 3 个字符后不同字符串的个数。
思路：
用 dp[ i ][ j ] 表示前 i 个字符中删去 j 个字符时拥有不同字符串的数量。
首先不考虑重复的情况，即可以得到转移方程------------------dp[ i ][ j ]=dp[ i ][ j-1 ]+dp[ i-1 ][ j-1 ]。
接下来考虑重复情况，如果相同字符出现在某个字符的前后三个字符以外，则不会有重复，只考虑在三个以内，假设现在在 i 位置，在该位置的前面的某个位置 k (要保证 i - k <=j )，此时 s[ k ]==s[ i ] , 此时长度为k 的字符串选择删除了s[k],还需要从长度为k-1的字符串中选择 j - (i - k )个字符去删除，那么在dp[ i ][ j ]中有 dp[ k - 1][ j - ( i - k )]个重复 即------------------------------------------------- dp[ i ][ j ]=dp[ i ][ j ]-dp[ k - 1 ][ j - ( i - k )] 。
代码：
#include<bits/stdc++.h>#define ll long long
#define MOD 998244353
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;ll dp[1000005][4];
char s[1000005];
ll sum=0;
int main()
{scanf("%s",s+1);dp[0][0]=1;int len=strlen(s+1);for(int i=1;i<=len;i++){for(int j=0;j<=3;j++){dp[i][j]+=dp[i-1][j];if(j>0)dp[i][j]+=dp[i-1][j-1];for(int k=i-1;k>=1&&i-k<=j;k--){if(s[k]==s[i]){dp[i][j]-=dp[k-1][j-(i-k)];break;}}}}for(int i=0;i<=3;i++)sum+=dp[len][i];cout<<sum;return 0;
}