Codeforces 1183H-Subsequences (hard version)

Codeforces 1183H-Subsequences (hard version)

题意

给一个长度为n的字符串s，要求找出k个不相同的子序列，每个子序列的花费是n-len（子序列长度），求最小花费。

题解

根据长度，找出所有长度为j的不同的子序列个数，然后长度再由大到小贪心的选取。
方法一：
dp[i][j]表示前i个字符中长度为j的子序列的数量。
根据选或者不选第i个字符进行划分，那么我们可以得到转移方程dp[i][j]=dp[i-1][j]+dp[i-1][j-1]。但是这样，在选第i个字符的方案中，显然包含了重复的子序列，考虑去重，记pre[i]为i的前驱，重复的部分就应该为dp[pre[i]-1][j-1]。
所以转移方程为dp[i][j]=dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[pre[i]-1][j-1]。

方法二：
dp[i][j]表示从i开始长度为j的不同的子序列个数。
考虑去重：只在相同字符第一次出现的地方惊醒转移。

方法一

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=110;
int n;
ll k,ans;
char s[N];
ll dp[N][N];
int pre[N],last[N];

int main(){
    scanf("%d%lld",&n,&k);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++){
        int x=s[i]-'a';
        if(last[x]) pre[i]=last[x];
        last[x]=i;
    }
    for(int i=0;i<=n;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]+dp[i-1][j-1];
            if(pre[i]) dp[i][j]-=dp[pre[i]-1][j-1];
        }
    }
    for(int i=n;i>=0;i--){
        ll cnt=min(k,dp[n][i]);
        ans+=cnt*(n-i);
        k-=cnt;
        if(k<=0) break;
    }
    if(k>0) ans=-1;
    printf("%lld\n",ans);
    
    return 0;
}

方法二

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=110; 
int n;
ll k,ans;
ll dp[N][N],len[N];
char s[N];
bool vis[N];


int main(){
    scanf("%d%lld",&n,&k);
    scanf("%s",s+1);
    for(int i=0;i<=n;i++) dp[i][1]=1;
    for(int j=2;j<=n;j++){
        for(int i=0;i<=n;i++){
            memset(vis,0,sizeof(vis));
            for(int k=i+1;k<=n;k++){
                int x=s[k]-'a';
                if(!vis[x]) dp[i][j]+=dp[k][j-1];
                vis[x]=1;
            }
        }
    }

    //包含空串的长度 
    k--;
    for(int i=n;i>0;i--){
        ll cnt=min(k,dp[0][i]);
        ans+=cnt*(n+1-i);
        k-=cnt;
        if(k<=0) break;
    }
    if(k>0) ans=-1;
    printf("%lld\n",ans);
    return 0;
}

Codeforces 1183H-Subsequences (hard version)

原文：https://www.cnblogs.com/qjy73/p/12524244.html