思维练习。依旧懒得打代码。
题意解析：给定 n 个字符串 Ai，请你将它们按任意顺序拼接，并求出拼接后所有可能的字符串中字典序最大的一个。n≤20,∣Ai∣≤10。
注意到题目让求的是字典序，所以我们就要尽量让前面的字符小的情况下让后面的字符小即可。
首先考虑不存在某个字符串是另一个字符串的前缀的情况。
显然有一个很显然的贪心：按字典序从大到小排序即可。证明显然。
然后再考虑总共的情况。
首先将 A 按字典序排序，然后按以下方法分组：
- 如果某个字符串是另一个字符串的前缀，则这两个分为一组。
显然会分成若干个区间，而只需要在每个区间内重排就可以得到答案。
现在专门考虑一个区间。例如：{dcbadda,...,dcbadcbabcd,...,dcbabcd,...,dcba}。
显然这个区间的答案为 dcba...dcba...dcba...dcba...，现在考虑每个空填什么。
因为求的是字典序最大值，所以：
- 如果除去前缀 dcba 后前缀不是 dcba，且字典序大于 dcba，则它一定在前面，分成一小组；
- 如果除去前缀 dcba 后前缀是 dcba，则得继续考虑它后面的字符，但一定比下面的优，放在中间，分成一小组；
- 如果除去前缀 dcba 后前缀不是 dcba，且字典序小于 dcba，则它一定在后面，分成一小组。
然后分别考虑这几个小组：
- 对于前面那一组和后面那一组，答案为 dcba...dcba...dcba...dcba...(dcba) 此时就相当于在后缀加上 dcba，加上这个串，继续按字典序排序，继续分组。
- 对于中间那一组，然后就变成了 dcbadcba...dcbadcba...dcbadcba...，将下一个 dcba 当成前缀，按字典序排序，分组。
显然最终每个字符串会分为一组，就能得出答案了。
应该是对的吧。
时间复杂度不知道，能过就行。
有帮助，赞一个