Subsequences (hard version)

题意:
给出一个长度为n的字符串和一个k,求形成k个不同子串组成的集合至少要删除多少字符?如果无法完成则输出-1.

思路:
动态规划:
dp[i][j]表示前i个字符组成一个长度为j的不同子串的数目;
dp[i][j]=dp[i-1][j] (不加第i个字符)+dp[i-1][j-1] (加第i个字符)+dp[ma[i]-1][j-1] (去重,ma[i]表示前面的最近的s[i]的位置,因为该位置前一个位置长度为(j-1)的子串加上该位置等与加上s[i])
初始换:dp[i][0]=1(0<=i<=n);
结果从删除少的向删除多的方向进行就可以了。

代码:

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

typedef long long ll;
const ll inf=1e12;
const int N=1000005;

string s;
int ma[1005];
ll dp[105][105];

int main()
{
    ll n, k;
    memset(ma,-1,sizeof(ma));
    scanf("%lld%lld",&n,&k);
    cin >> s;
    for(int i=0;i<=n;i++)
    {
        dp[i][0]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            if(ma[s[i-1]]!=-1)
            {
                dp[i][j]=dp[i][j]-dp[ma[s[i-1]]-1][j-1];
            }
        }
        ma[s[i-1]]=i;
    }
    ll ans=0;
    for(int i=n;i>=0;i--)
    {
        k=k-dp[n][i];
        ans=ans+dp[n][i]*(n-i);
        if(k<=0)
        {
            ans=ans-(-k)*(n-i);
            break;
        }
    }
    if(k>0)
    {
        printf("-1");
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}
每日一题题解 文章被收录于专栏

写题解

全部评论

相关推荐

当年还在美团那个倒霉的&nbsp;Peppr&nbsp;团队工作时,我一直有个疑问:这群人每天到底在自嗨什么。每次开会一堆人围着一堆“看起来很高级”的文档转,模板统一、名词复杂、页数感人,每一页都在暗示一件事:“你不懂,是因为你不专业。”但现实是——代码照样写在&nbsp;💩&nbsp;山上,该出问题还是会出问题,这真的很逗,系统一出问题,文档的唯一作用就是证明:“我们当初确实认真写过文档。”所以本质区别到底是什么?是代码质量提升了,还是大家在精神层面完成了一次“工程师&nbsp;cosplay”?有句话说得好潮水退去才知道谁在裸泳。还记得当时的马哥、明哥(图&nbsp;1&nbsp;左)最爱反复强调一句话:“所有场景一定要想到。”、“这个场景为什么没考虑到?”不过他们这些话我是真的听进去了。不然我也不会在一年多前就说:这个项目活不过两年。顺带一提,那段时间还有个固定节目。每次下楼,总能听见我明哥在吐槽不同的人。我从他身后绕过去,经常能听到他一边抽烟一边说:“xx&nbsp;这小子太坑了,回头我一定要跟马哥说说。”于是深谙人情世故但真不会抽烟的我也会从口袋掏出一支低尼古丁含量的烟给自己点上,假意自己什么都没听到什么都不知道,只是来抽烟的。后来我才明白,这可能也是团队文化的一部分:问题永远在别人身上,而我们,永远在复盘里😂。
秋招白月光
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务