题意
给你 \(n\) 个串 \(s_i\)，你需要选出 \(k\) 个串并按照某个顺序拼接起来形成的字符串字典序最小。
\(n,k,|s|\le 50\)。
分析
由于顺序不固定，所以我们无法直接 DP。而状压的复杂度也太高了，怎么办呢？
考虑钦定一个顺序，使得按照这个顺序排列字符串一定最优。
一个经典的错误想法是：将字符串按照字典序升序排序。
hack：ba b，最优排列是 bab，但由于 b<ba，所以我们的程序会得出 bba 的结果。
考虑 exchange argument 贪心，设字符串 \(s,t\) 交换后一定不优，那么我们有 \(s+t\le t+s\)。事实上，以 \(s+t<t+s\) 排序是正确的。为什么呢？
考虑把这两个字符串写成哈希的形式，即 \(F(s)=\sum_{i=0}^{len} p^{len-i}s_i\)，\(F(t)\) 同理。我们写出 \(F(s+t),F(t+s)\)，首先注意到这两个串长度相等，那么 \(s+t<t+s\) 当且仅当 \(F(s+t)<F(t+s)\)，而 \(F(s+t)=p^{|t|}F(s)+F(t),F(t+s)=p^{|s|}F(t)+F(s)\)，所以有 \(p^{|t|}F(s)+F(t)<p^{|s|}F(t)+F(s)\)，移项得 \(\dfrac{F(s)}{p^{|s|}-1}<\dfrac{F(t)}{p^{|t|}-1}\)，发现等式两边只跟 \(s,t\) 有关，而且由于这是数值，所以天然具有传递性、自反性。于是这样排序就是对的了。
关于 DP，我们仍然有一个经典错误想法：设 \(f_{i,j}\) 表示前 \(i\) 个串中选了 \(j\) 个串的最小字典序，转移 \(f_{i,j}=\min(f_{i-1,j},f_{i-1,j-1}+s_i)\)。hack 考虑 ba 和 b 两个串，它们之后都要接 qwqwq 这个串，不难发现 baqwqwq 是字典序最小的，但由于 b 字典序比 ba 小，所以 DP 出来的方案是 bqwqwq，本质上是因为当字符串长度不相同时，我们只考虑一开始的字典序大小关系，而没有考虑拼上字符串后的字典序大小关系。也就是说，若要从前往后取，为了保证字典序比较正确，我们还需要记录一维状态表示取的字符串长度，这样复杂度五方，就又上天了。
这种正着 DP 要记录很多额外状态的题，有一种经典方案是考虑倒着 DP。设 \(f_{i,j}\) 表示 \(i\sim n\) 这些串选 \(j\) 个拼成的最小字典序。这样我们就把字符串长度的状态扔掉了（由于是向前拼接所以对字典序大小关系必然不影响），转移方程类似，复杂度四方。
代码非常好写：
const int maxn=55;
int n,k;
string s[maxn],f[maxn][maxn];
bool cmp(string x,string y){return x+y<y+x;}
void solve_the_problem(){
cin>>n>>k;
rep(i,1,n)cin>>s[i];
sort(s+1,s+n+1,cmp);
rep(i,1,n)f[i][1]=s[i];
per(i,n-1,1)rep(j,2,n)rep(k,i+1,n)if(f[k][j-1]!=""){
string res=s[i]+f[k][j-1];
if(f[i][j]=="")f[i][j]=res;
else f[i][j]=min(f[i][j],res);
}
string ans=f[1][k];
rep(i,2,n)if(f[i][k]!="")ans=min(ans,f[i][k]);
cout<<ans;
}