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

题目

题目链接

题解

动态规划。

状态表示：f[i][j]表示前i个字符删除j个后不同的字符串数。

首先简单考虑一下，对于第i个字符，我们可以选择删除或者不删除，即f[i][j] = f[i-1][j-1] + f[i-1][j]

看个例子cdabnaxy，删除abn和删除bna后得到的字符串都是cdaxy，说明存在多统计的情况，那么我们要减去这些重复的情况。

根据上面那个例子可以发现对于一个字符s[i]，如果在i之前存在一个x使得s[x]=s[i]，那么删除[x,i-1]间的字符和删除[x+1,i]间的字符其实是重复的，等价的，那么f[i][j]就要减去f[x-1][j-(i-x)]，减去删除这段造成的重复串。

代码

#include
using namespace std;
typedef long long LL;
const int N = 1e6+10;
string s;
int n, last[N];
LL ans, f[N][5];
int main()
{
	cin >> s;
	s = '.' + s;
	for (int i = 0;i