题解：AT_abc225_f [ABC225F] String Cards

· · 题解

多头讲的题目。

我们先考虑假设所有数都要选怎们做，一个很简单的想法是直接按字典序排序，但是随便手玩一下这个就是错的，想一想为什么是错的，因为你的前缀不一定能确定大小，我们对两个字符串 a,b，我们直接比较 a+b 和 b+a 的大小。正确性显然，对于 n 个的情况，以为有延续性就可以得证了。这叫做临项交换法。

前面这个东西非常有启发性，因为前缀不行，但是后缀是可以的。我们直接设 dp_{i,k} 表示已经填完了 \left[i,n\right] 这个区间，选了 k 个的答案（显然是后缀，由上文知道前缀是错的），我们直接转移就行了。

submissions