题解 CF1183H Subsequences (hard version)

瞎搞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)$ 的，但是过了就行）。

代码

#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);
}

Dilute

题解 CF1183H Subsequences (hard version)

瞎搞DP

代码