题解：AT_abc225_f [ABC225F] String Cards

首先很容易想到这一题：P1012。
这一题里面用到了一个贪心策略：按照这个方式排序 $a+b>b+a$
于是一开始的思路直接照做，排完序取前 $k$ 个，然后喜提 WA。

考虑一下问题出在哪，很显然，P1012 最终得到的字符串长度是固定的，但本题不是，比如下面这组数据，就会因为答案字符串的长度而寄：

3 2
bba
bb
bba

按照原先的思路会这样排序：bba bba bb，然后就挂了。

那就 DP 吧。

不难想到状态 $dp_{i,j}$ 是考虑到第 $i$ 个字符串时取 $j$ 个字符串的答案，但因为如果考虑的是 $[1,i]$ 的话仍然会被字符串长度背刺，而考虑 $[i,n]$ 就没问题了。

但在转移前我们首先要排序，这样可以更方便的求出答案，这种技巧叫做 exchange argument，用和 P1012 一样的方式就行了。
转移很简单，每个字符串选或不选，有 $dp_{i,j}=\min(s_i+dp_{i+1,j-1},dp_{i+1,j})$
只用考虑把 $s_i$ 放在 $dp_{i+1,j-1}$ 前面的情况就够了，由于我们排过序，所以 $dp_{i+1,j-1}+s_i$ 一定大于 $s_i+dp_{i+1,j-1}$。
同时也有边界条件 $dp_{n,1}=s_n$。

记得初始化。