给你 \(n\) 个字符串，要求你选择 \(k\) 个字符串以任意顺序拼在一起，使最终的字符串字典序最小，输出最终字符串。

\(n,k,|s|\leq50\)

一个非常显然的 DP ：\(dp[i][j]\) 表示前 \(i\) 个串选了 \(j\) 个的最小字典序串，用上字典序的经典 trick ，每次转移把新串拼在前面。

但问题就在于可以任意顺序插入，必须给 \(n\) 个串先定个顺序。

字典序从大到小？ FAKE 。反例： \(ca,c\) 。

考虑排序是干嘛，其实就是为了任意两段交换不会更优，所以我们定义字符串 \(s < t\) ：字典序下 \(st < ts\) 。

为什么这样可以排序？

把字符串换成 \(26\) 进制数。由于 \(|st|=|ts|\)，所以字典序下 $ st<ts$ 等价于 \(26\) 进制下的 $ st<ts$ 。所以有以下式子：

$st<ts $
\(\Leftrightarrow s \times 26^{|t|} +t< t\times 26^{|s|}+s\)
\(\Leftrightarrow \frac{s}{26^{|s|} - 1} < \frac{t}{26^{|t|} - 1}\)

所以实质上由上述方法排序是对 \(s_i\) 以 \(\frac{s_i}{26^{|s_i|} - 1}\) 为关键字排序，满足偏序要求。

这种排序确实是字符串拼接定顺序的好方法。

搬运自 Luogu Blog