思路
Part 1 弱化版
看到这道题的第一眼想到了 P1012 这道题。
但是，这两道题选择的数量是有区别的。
我们可以由拼数得出一个结论性的排序规则（这里就不多做解释了）：
inline bool cmp(string a,string b){
return a + b < b + a;
}
如果用这样的做法，有 hack。
Part 2 状态定义
我们首先可以定义状态 \(dp_{i,j}\) 为在前 \(i\) 个字符串中取 \(j\) 个字符串字典序最小的结果。
我们便能很轻松的得出以下状态转移方程：
\[ dp_{i,j} = \min(dp_{i - 1,j},dp_{i - 1,j - 1} + s_i) \]但是，仔细一看就能发现一些问题：在你搞字典序最小的字符串时，是不是先确定前面的字符串再确定后面的字符串吗？计算机也是这样的。
所以，我们修改状态函数 \(dp_{i,j}\) 表示在后 \(i\) 个字符串中取 \(j\) 个字符串字典序最小的结果。
状态转移方程为：
\[ dp_{i,j} = \min(dp_{i + 1,j},s_i + dp_{i + 1,j - 1}) \]Part 3 整理
我们由拼数这道题可以再次得出一个结论：如果假设按照上述排序规则排序后，要使自字典序最小的字符串序列为 \(s_{a_1},s_{a_2},\dots,s_{a_k}\)，那么 \(a\) 序列必定是严格单调递增的。
那么，这题何尝不是呢？
所以，我们要在执行 DP 前，按照上述排序规则排一次序。时间复杂度为：\(\Theta(n\log n + nk)\)。
Code
#include <bits/stdc++.h>
#define re register
using namespace std;
const int N = 60;
int n,k;
string s[N];
string dp[N][N];
inline 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 (re int i = 1;i <= n;i++) cin >> s[i];
sort(s + 1,s + 1 + n,cmp);//排序
for (re int i = 1;i <= n;i++){//将 dp 数组初始化为正无穷
for (re int j = 1;j <= k;j++) dp[i][j] = "{";//因为 '{' 的 ASCII 码比 'x' 的大
}
dp[n][1] = s[n];//状态起点
for (re int i = n - 1;i;i--){//转移
for (re int j = 1;j <= k;j++) dp[i][j] = min(dp[i + 1][j],s[i] + dp[i + 1][j - 1]);
}
cout << dp[1][k];
return 0;
}