Subsequences (hard version)

CI_is_safe · 2023-02-26 19:47:49 · 个人记录

Subsequences (hard version)

思路

考虑令 f_{i,j} 表示前 i 个字符构成长度为 j 的子序列的个数。显然 f_{i,j}=f_{i-1,j-1}+f_{i-1,j}，但是会有重复。比如 abcac，会构成两个 abc，这时考虑记录当前这个字符上次记录的位置 pre_i，f_{i,j}-=f_{pre_i-1,j-1} 即可。 处理完后，就可以贪心了，删的越少费用越少，可以按照长度从大到小枚举，能填则填。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
int n,m,pre[26],f[N][N];
char s[N];
signed main(){
    scanf("%lld%lld%s",&n,&m,s+1);
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        f[i][0]=1;
        for(int j=1;j<=n;++j){
            f[i][j]=f[i-1][j-1]+f[i-1][j];
            if(pre[s[i]-'a'])f[i][j]-=f[pre[s[i]-'a']-1][j-1];
        }
        pre[s[i]-'a']=i;
    }
    long long ans=0;
    for(int j=n;j>=0;--j){
        if(m>=f[n][j]){
            ans+=1ll*(n-j)*f[n][j];
            m-=f[n][j];
        }
        else{
            ans+=1ll*(n-j)*m;
            m=0;
            break;
        }
    }
    if(m)puts("-1");
    else printf("%lld",ans);
    return 0;
}