Subsequences (hard version) 题解(dp求不重复子序列)

题目链接

题目大意

给你一个长度为 $n(n \leq 100)$ 的字符串

要你找出 $k(k \leq 10^{12})$ 个不同的子序列，使得k个不同的子序列总价值最小是多少

一个子序列的价值为删去的字符长度

空串也为子序列

题目思路

其实不难就是要明白怎么设dp方程

设 $dp[i][j]$ 为前i个字符构造长度为j的不同子序列长度

显然 $dp[i][j]=dp[i-1][j]+dp[i-1][j-1]$

就是选和不选第i个字符的问题

但是会有重复

假设我们之前有个序列是staxya，那么如果我们现在选的是i=6,j=2的情况，如果我们直接按照上面计算我们就会选择前5个选1个字母和a组合，会出现sa,ta这种情况，还会选择直接前面5个数直接组成2个字母的情况。那么又会计算到sa,ta这种情况，那么多出来的部分是不是就是选定最近出现的位置并且保证这个字母必选的前提下，去前面再选j-1个字母呢，好了到这里我们就吧全部的问题解决了。

参考：https://blog.nowcoder.net/n/f7b66bc412114f1e881d6d22c6f6e7c0

$dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[last[i]-1][j-1]$

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e2+5,inf=0x3f3f3f3f;
const int eps=1e-3;
const ll mod=1004535809;
int n;
ll k;
int last[maxn];
int asc[300];
ll dp[maxn][maxn];
char s[maxn];
signed main(){
    cin>>n>>k;
    cin>>s+1;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        last[i]=asc[s[i]];
        asc[s[i]]=i;
        dp[i][0]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            if(last[i]!=0){ //表示前i-1个有s[i]字符
                dp[i][j]-=dp[last[i]-1][j-1];
            }
        }
    }
    ll ans=0;
    for(int j=n;j>=0;j--){
        if(dp[n][j]<k){
            ans+=dp[n][j]*(n-j);
            k-=dp[n][j];
        }else{
            ans+=k*(n-j);
            break;
        }
        if(j==0) ans=-1;
    }
    cout<<ans<<endl;
    return 0;
}