Subsequences (hard version)
Subsequences (hard version)
https://ac.nowcoder.com/acm/problem/113788
比较妙的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;
}
美的集团公司福利 816人发布
投递哔哩哔哩等公司6个岗位