本周无团队训练

ABC175 pros:5/6/6 TCO20 Round3B pros0/1/3

没有专题

没有比赛

没有专题

没有比赛

ABC175F

tag:回文串、dp

题意：N($N \leq 50$)个字符串($|S_i| \leq 20$)，每个字符串有一个代价$c_i$，问每个串可以不限次数使用的情况下用这N个字符串拼接出一个回文串的最小代价。

解法：枚举最终回文串的对称轴。对于每个串，枚举每个可能的位置作为对称轴，则一定会剩一段前缀或者后缀没有匹配，并且一定存在另一个串接在另一端来匹配这个子串。计$dp_{i,j,1}$为待匹配为第i个串的第j个前缀的最小代价，$dp_{i,j,2}$为第i个串的第j个后缀的最小代价，转移时参考dijkstra的思想，初始化后每次取出优先队列队首的状态，计算出所有可达状态并推入优先队列，不断重复直到优先队列取出空串。时间复杂度$O(N^2*|S|*log(N*|S|))$