CF1183 H.Subsequences (hard version)【线性DP】

题目链接：codeforces1183H Subsequences (hard version)

题解

求前 长的子序列。定义dp[i][j] 为前 个长度为 的子序列个数，首先将 dp[i-1][j] 的状态转移到 dp[i][j]，再加上不包含当前 s[i] 的子序列个数，即 dp[i-1][j-1]。又因为前面可能会有 s[last] 与 s[i] 相等，我们只要减去 dp[last-1][j-1] 即可，last 是在 前面离 最近的相等字符的下标。

参考代码

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
#include <iostream>
using namespace std;
typedef long long ll;
char s[110];
ll dp[110][110];
int pre[110];
int main() {
    ll n, k;
    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] != 0) dp[i][j] -= dp[pre[i]-1][j-1];
        }
    }
    ll ans = 0;
    for (int i = n; i >= 1 && k; i--) {
        ans += min(dp[n][i], k) * (n-i);
        k = max(0LL, k-dp[n][i]);
    }
    if (k > 1) cout << -1 << endl;
    else {
        if (k == 1) ans += n;
        cout << ans << endl;
    }
    return 0;
}