题解：AT_abc225_f [ABC225F] String Cards

· · 题解

begin

思路

第一眼：建议降红。

第二眼：满江红。。。。。。。

首先我们可以想到一个看似正确实则错误的贪心思路：

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

在这组数据下直接被打爆：

input:
3 3
bab
bab
bb

example_output:
babbb

my_output:
babbab

基于以上思路我们继续将思维发散到动态规划。

我们定义 f_{i,j} 为从 S_i \sim S_n 中取 j 个字符串组成的字典序最小的字符串。

那么显然有：

f_{i,j}=\min(f_{i+1,j},S_i+f_{i+1,j-1})

边界条件：

f_{n,1}=S_n

最后答案：

f_{1,k}

Tips

注意 S_i 是加在前面的，而且我们要从后往前枚举 i。

Code

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,k;
string s[60],f[60][60];
bool cmp(string a,string b){return a+b<b+a;}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for (ll i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+n+1,cmp);
    for (ll i=1;i<=n;i++) for (ll j=1;j<=k;j++) f[i][j]=(char)('z'+1);
    for (ll i=n;i>=1;i--)
    {
        if (n==i)
        {
            f[i][1]=s[i];
            continue;
        }
        for (ll j=1;j<=k;j++)
        {
            f[i][j]=min(s[i]+f[i+1][j-1],f[i+1][j]);
        }
    }
    cout<<f[1][k];
    return 0;
}

end