题解：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。

记得初始化。