主要思路:dp[i][j]表示在前i个字符中删除j个字符是字符串种类数,则dp[i][j]分为两种情况删除第i个字符,不删除第i个字符:dp[i - 1][j],删除第i个字符:dp[i - 1][j - 1],所以dp[i][j = dp[i - 1][j] + dp[i - 1][j - 1],然后再考虑重复情况,以样例举例ababcc删除第1,2个元素ab和删除第2,3个元素ba剩余元素都为abcc,再举一个例子abcade,这时删除abc和删除bca剩余元素都为ade,所以我们应该从k = i - 1个元素开始查询s[k] == s[i]的元素,同时k>=1并且j >= (i - k),因为最多删除j个元素,所以此时dp[i][j] = dp[i][j] - dp[k - 1][j - (i - k)]
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
using namespace std
;
const int N
= 1000010;
long long f
[N
][4];
char s
[N
];
int main(void)
{
scanf("%s", s
+ 1);
int len
= strlen(s
+ 1);
f
[0][0] = 1;
for(int i
= 1; i
<= len
; i
++)
{
for(int j
= 0; j
<= 3; j
++)
{
if(j
> 0) f
[i
][j
] += f
[i
- 1][j
- 1];
f
[i
][j
] += f
[i
- 1][j
];
for(int k
= i
- 1; k
>= 1 && i
- k
<= j
; k
--)
{
if(s
[k
] == s
[i
])
{
f
[i
][j
] -= f
[k
- 1][j
- (i
- k
)];
break;
}
}
}
}
long long sum
= 0;
for(int i
= 0; i
<= 3; i
++) sum
+= f
[len
][i
];
cout
<< sum
<< endl
;
return 0;
}```