抽卡 | Bzdhxs'blog

题目描述

有 $n$ 张卡片，每张卡片上有一个字符串 $s_i$ , 现在要求你从中选出 $k$ 张卡片，使得在所有选取方案中，这 $k$ 张卡片连起来的字典序是最小的

思路

根据以下规则排序

1
2
3

bool cmp(string a,string b){
    return a + b < b + a;
}

排序后

为什么不选前 $k$ 个？
当 $k = 1,s = \{ba,b\}$ 排序后就会得到 $ba$ 的字典序小于 $b$ 的错误结果

考虑 $f[i]$ 表示为以第i个字符串结尾的最小字典序

倒着跑一边01背包(某个字符串选或不选)

为什么不正向跑呢？

模拟一下样例

4 3
bbaba
bba
b
b

The answer for the following case is bbababb, but it outputs bbababbab.

错误答案前缀覆盖了正确答案,在正向dp的过程中无法对长度进行更改

Code

int n,m;
string s[55];
string f[55];
bool cmp(string a,string b){
    return a+b < b+a;
}
signed main()
{
    cin>>n>>m;
    forr(i,1,n) cin >> s[i];
    forr(i,1,54) f[i] = "{";
    sort(s+1,s+1+n,cmp);
    for(int i = n;i>=1;i--)
        for(int j = m;j >=1;j--)
            f[j] = min(f[j],s[i]+f[j-1]);
    cout << f[m] << endl;
    return 0;
}