题解：AT_abc225_f [ABC225F] String Cards

· · 题解

前言

做这道题之前可以先去看看 P1012。

思路

想到特殊的排序方式。
当且仅当 s_i+s_j\le s_j+s_i 时，s_i 排在 s_j 的前面。
然后就很容易陷入误区，并不是选排在最前面的就最优。 不理解就看下面这个例子：

3 2
za
z
za

排序后的顺序为 za za z，如果直接选前两个构成的字符串为 zaza 很明显不如 zaz 更优。
所以我们考虑动态规划，设 f_{i,j} 表示 [i,n] 中取 j 个字符串形成的字典序最小的字符串。
状态转移方程为：

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

因为是排好序的，所以 s_i+f_{i+1,j-1} 肯定比 f_{i+1,j-1}+s_i 更优。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=60;
int n,k;
string s[N],f[N][N];
bool cmp(string x,string y){return x+y<y+x;}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+1+n,cmp);
    for(int i=1;i<=n+1;i++) for(int j=1;j<=k;j++) f[i][j]='~';//'~'是一个ASCII比'z'大的字符
    f[n][1]=s[n];
    for(int i=n-1;i>=1;i--) for(int 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;
}