Subsequences (hard version)

比较妙的DP题
设计dp[i][j]表示前i个字符中选j个字符可以构成的方案
pre[i]代表ascall为i的字符上一次出现的位置
转移方程有容斥的思想,如下
dp[i][j]=j==0?dp[i-1][j]:dp[i-1][j]+dp[i-1][j-1]-dp[(pre[a[i]]-1)==-1?n:(pre[a[i]]-1)][j-1];
再贪心统计一下答案即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,dp[105][105],pre[205];
char a[105];
signed main()
{
    scanf("%lld%lld",&n,&k);
    scanf("%s",a+1);
    dp[0][0]=1;
    for(int i=1;i<=n;pre[a[i]]=i,i++)
        for(int j=i;j>=0;j--)
            dp[i][j]=j==0?dp[i-1][j]:dp[i-1][j]+dp[i-1][j-1]-dp[(pre[a[i]]-1)==-1?n:(pre[a[i]]-1)][j-1];
    int ans=0;
    for(int i=n;i>=0&&k;i--){
        ans+=min(k,dp[n][i])*(n-i);
        k-=min(k,dp[n][i]);
    }
    if(k) ans=-1;
    cout<<ans<<"\n";
    return 0;
}