CF1183H Subsequences (hard version) 题解

CF1183H Subsequences (hard version)

题意：

给定一个长度为 $n$ ( $n <= 100$ ) 的字符串 $s$ 以及一个数字 $k$ ( $k <= 10^{12}$ )，规定串的每个子序列的价值为 $n - len$ ，现在要求你求出 $k$ 个本质不同的子序列使得价值最小。

ps.本质不同指的是：子序列的内容不同，而不是单纯的子序列的位置不同。

具体做法

这是一道不难的 $dp$ 。

不难发现题目的意思实际上就是让我们求长度为前 $k$ 长的本质不同的子序列，找出每个长度对应有多少个本质不同的子序列即可。

所以问题就在于找本质不同的子序列。

怎么找呢？遇事不决， $dp$ 来解。

考虑设置状态如下:

$dp[i][j]$ 表示的是原串的前 $i$ 个字符中长度为 $j$ 的本质不同的子序列数量。

接下来就要想如何转移了。

在做 $dp[i][j]$ 的时候，我们默认已经求出来了 $dp[i - 1][1$ ~ $n]$ 。我们现在要考虑怎么样才能利用已知的信息推出当前信息。

不难发现， $dp[i - 1][j]$ 表示的就是前 $i - 1$ 个字符中长度为 $j$ 的本质不同的子序列数量。我们可以选择从它这里继承过来，不往这些字串后面加上当前字符，所以可以通过它来得到 $dp[i][j]$ 。

然后 $dp[i - 1][j - 1]$ 要转移为 $dp[i][j]$ ，那么前面所有串的末尾都要加上当前字符。但是我们又可能算重复，也就是可能会导致求出来的子序列有部分不满足是本质不同的子序列。于是我们要考虑容斥掉其中一部分。这一部分是什么呢？

不难发现是 $dp[pre[i] - 1][j - 1]$ ( $pre[i]$ 表示的是前一个跟当前字符相同的字符的位置)，因为 $dp[pre[i] - 1][j - 1]$ 得到的所有子序列都跟当前串是本质相同的。

于是状态转移方程 : $dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - dp[pre[i] - 1][j - 1]$ (最后一项当且仅当当前字符存在前驱的时候才会有)

最后我们显然选择长度为前 $k$ 的子序列计算答案即可。

时间复杂度:O( $n ^ 2$ )

具体实现放代码里面了。

Code

// Problem: CF1183H Subsequences (hard version)
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL k;
char s[105];
LL dp[105][105],pre[105];//前1~i个字符，长度为j，本质不同的字串的数量

int main() {
    cin >> n >> k >> (s + 1);
    for(int i = 1 ; i <= n ; i ++) {
        for(int j = i + 1 ; j <= n ; j ++)
        if(s[i] == s[j]) pre[j] = i;
    }
    for(int i = 0 ; i <= n ; i ++) dp[i][0] = 1;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= i ; j ++){
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            if(pre[i]) dp[i][j] -= dp[pre[i] - 1][j - 1];
        }
    LL Ans = 0;
    for(int j = n ; j >= 1 && k; j --) {
        Ans += min(dp[n][j],k) * (n - j) ;
        k = max(k - dp[n][j],0ll);
    }
    if(k > 1) {printf("-1"); return 0;}//之所以是 k > 1是因为要考虑空串
    if(k == 1) Ans += n;//没有考虑空串，所有要考虑一下
    cout << Ans;
    return 0;
}