这是本文档旧的修订版!
date: 2020.07.05 13:00-18:00
题目大意:给一个串,$n\le3000$,$\Sigma\le70$。问将这个串重排后回文子串数量的最大值,以及达到该数量的重排方案数。
题解:考虑所有回文子串的集合和所有相同字符对的集合。容易注意到前者有一到后者的单射。因而回文子串数量 $\le$ 相同字符对的数量。而当所有相同字符排列在一起时,能取到最大值。
接下来考虑有哪些其它 pattern
也能达到最大值。首先一个字符可以如前所述全部排在一起。除此之外,若一个字符 a
有三个以上,首先它们自己的位置必须成一等差数列,其次相邻两个 a
之间的串都相等,且是回文串。考虑 a***a***a
,第一个 a
后的 *
和第二个 a
后的 *
应当相等,这将导致第一个 a
后的第二个 *=a
,矛盾。因此相邻 a
之间只能是单个字符,即 ababab...
的模式。对于有两个的字符,还可以包在某个回文串的外部,如 abcbcba
。只有一个的字符,要么单独排列,要么被若干有两个的字符包围,如 abcba
。
使用 $dp$ 计数。考虑出现次数从大到小转移。设 $dp[i][j][k][u][v]$,表示当前字符出现次数为 $i$,已经使用出现 $i$ 次的字符 $j$ 个,已经使用出现 $i-1$ 次的字符 $k$ 个,有 $u$ 个回文串,$v$ 个非回文串。
其中 $i,j$ 可滚动。时间复杂度 $O(\Sigma^{4})$。