比较妙的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; }