CF 286 div1

题意极为简单,给定一个串,长度为,考虑在任意位置加入个字符,求算形成回文串的方案总数。

暴力DP

想想暴力或许是有用的。考虑一个类似区间DP的思路。设表示构造出来的新串前面和后面都有个字符,且满足回文,此时用中的字符从左起一共用个进行匹配,从右起用个进行匹配。
然后显然就是枚举当前我们用字符加在左端的尾巴或者右端的前面。
- 考虑时。
1. 即考虑上次,就已经匹配过了,然后这一次我们加一对不同的字符进去【一共25种】
2. 即这一次我们直接匹配了这一对字符。
- 考虑时。
1.
2.
这两种情况就是我们加入一个字符与左右某一边进行匹配。
3. 同情况1的2。

dp方程的实质

对于串处理的问题,我们不由得想到了自动机。
考虑样例建立如下自动机。


我们发现自动机每走一步就是对应了一种转移。
我们用红点和绿点来区分上述两种情况。因为这两种情况的转移是不同的。
当然还存在一个蓝色节点。GOAL显然这个东西就是自己转移到自己。

优化自动机。

我们发现所有红点的转移相同,所有绿点的转移相同。而且转移和转移顺序并无关系。我们只需统计一下n1个红点和n2个绿点的路径个数。这个东西看起来是可以算的。当然在优化的时候我们

Recent Posts

comments powered by Disqus