题解

思路推导

每个字符串只有原串和反转串两种状态。当前字符串能采用哪种状态，只取决于前一个字符串采用的状态，因此可以沿输入顺序做动态规划。

设 $dp_{i,0}$ 表示前 $i$ 个字符串已经合法排列且第 $i$ 个字符串不翻转时的最小代价，$dp_{i,1}$ 表示第 $i$ 个字符串翻转时的最小代价。对于前一位置的两种状态，分别比较对应字符串是否不大于当前候选字符串；满足字典序条件时即可转移，并在当前翻转时加上 $c_i$。

做法

预先保存每个原串及其反转串。初始化第一个字符串的两个状态为 $0$ 和 $c_1$，随后逐个计算四种相邻状态组合。不可达状态记为无穷大。最终取最后两个状态的较小值；若都不可达则输出 $-1$。

在 $n\le 20$ 时，可以枚举全部 $2^n$ 个翻转集合并检查。若所有翻转代价均为零，则问题只需判断是否存在合法状态序列，可以把最小费用状态改为布尔可达状态。独立核验程序还可把两个状态视为分层图节点，求从首层到末层的最短路。

正确性证明

任意合法方案在位置 $i$ 的选择只有原串或反转串，并且全局非递减条件等价于每一对相邻字符串都非递减。动态规划枚举了前一位置和当前位置的全部四种状态组合，只在相邻比较合法时转移，所以每条状态路径对应一个合法翻转方案。

反之，任意合法翻转方案的相邻状态都满足某次转移条件，因此它会被动态规划生成；转移累计的恰是被翻转字符串的代价。对每个状态取最小值后，末层最小值就是所有合法方案中的最小总代价。若末层不可达，则不存在合法方案。

复杂度分析

每对相邻字符串只进行常数次字典序比较，总时间复杂度为 $O(L)$，其中 $L$ 为所有字符串总长度；额外空间复杂度为 $O(L)$。