瞎搞DP

CF出了H没出G 菜的真实

发现$k$从$\texttt{E}$题的$100$变成了$O(10^{12})$,考虑与$k$复杂度无关的做法。

我们考虑$f_{i, j}$表示以$s_i$开始,本质不同的长度为$j$的子序列数量。

显然直接转移是错误的,例如下面这种情况就会在计算字符串$\texttt{baa}$的$f_{1, 2}$的时候把$\texttt{ba}$给计算两遍。

我们考虑如何去掉这些重复算的字符串。

首先,我们枚举下一个出现的位置$u$,考虑$f_{u, j - 1}$被算重的条件。

如果存在一个$k$,使得$s_k = s_j$且$i < k < u$,那么我们发现$f_{k, j - 1}$完全包含的$f_{u, j - 1}$,换句话说就是$f_{u, j - 1}$整个算重了。

也就是说,我们在枚举转移的时候,我们只需要选择$s_u$是在$(l, n]$这段区间内第一次出现的$f_{u, j - 1}$转移即可。

求出了$f$之后,我们可以得出长度为$len$的本质不同的子序列就是$f[0][len + 1]$。

我们只需要从高到低枚举$len$,然后贪心的尽量取长的字符串即可。

最终复杂度$O(n^3)$(其实是可以做到$O(26 n^2)$的,但是过了就行)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647

ll inp(){
char c =getchar();
while(c < '0' || c > '9')
c = getchar();
ll sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}

ll f[200][200];
bool used[30];
char s[200];

int main(){
int n = inp();
ll k = inp();
scanf("%s", s + 1);
for(int i = 0; i <= n; i++)
f[i][1] = 1;
for(int len = 2; len <= n + 1; len++){
for(int i = 0; i <= n; i++){
memset(used, false, sizeof(used));
for(int j = i + 1; j <= n; j++)
if(!used[s[j] - 'a']){
used[s[j] - 'a'] = true;
f[i][len] += f[j][len - 1];
f[i][len] = std::min(f[i][len], k);
}
}
}
ll ans = 0;
for(int i = n; i >= 0; i--){
ll sum = f[0][i + 1];
memset(used, false, sizeof(used));
if(k > sum){
k -= sum;
ans += (n - i) * sum;
} else {
ans += (n - i) * k;
k = 0;
}
}
if(k > 0){
printf("-1\n");
return 0;
}
printf("%lld\n", ans);
}

 评论