题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805046946938880
题意：给定一个长度<=106的字符串，求至多删3个字符可以得到多少种不同的字符串。
思路：很明显这是一道dp题，但我想了好久也想不出来，试过用dfs暴力去解，然后过了两个点，得了16分。看了别人的思路后明白了本题的dp做法。定义dp[maxn][4]，dp[i][j]表示前i个字符删掉j个字符可以形成多少种字符串，可以很简单地得出dp[i][j]=dp[i-1][j-1]+dp[i-1][j]，即对第i个字符删或不删的两种情况。这是对一般情况，其中还有一些可能出现重复的情况需要删掉：每一次将可能重复的情况全部删掉，那么每一次只用考虑第i个字符可能出现的重复的情况; 例如abcded，对于i=6时，计算dp[6][1]时不会有重复; 计算dp[6][2]时，若删掉ed，与删掉de出现重复，需要减掉删掉ed的情况，删掉ed，即前3个删0个，所以应减dp[3][0]; 计算dp[6][3]时，若删掉ed和abc中的一个，与删掉de和abc中的一个重复，需要减去前一种情况，即删掉前3个中的1个，应减dp[3][1]。
那么不访用pos数组表示每个字符上一次出现的位置，记为tmp，若tmp>0（数组从下标1开始）且j-(i-tmp)>=0时：dp[i][j]-=dp[tmp-1][j-(i-tmp)]。（其中i-tmp即上例中的2,j-(i-tmp)即前tmp-1个数应删掉的字符。另外，最终结果可能超过int表示的范围，所以需用long long。
AC代码：
1 #include2 using namespace std; 3 4 const int maxn=1000005; 5 typedef long long LL; 6 char s[maxn]; 7 LL dp[maxn][4]; 8 int pos[30]; 9 10 int main(){11 scanf("%s",s+1);12 int len=strlen(s+1);13 for(int i=0;i<=len;++i)14 dp[i][0]=1;15 for(int i=1;i<=len;++i){16 int tmp=pos[s[i]-'a'];17 pos[s[i]-'a']=i;18 for(int j=1;j<=3;++j){19 dp[i][j]=dp[i-1][j-1]+dp[i-1][j];20 if(j-(i-tmp)>=0)21 dp[i][j]-=dp[tmp-1][j-(i-tmp)];22 }23 }24 printf("%lld\n",dp[len][0]+dp[len][1]+dp[len][2]+dp[len][3]);25 return 0;26 }