题解：P12837 [蓝桥杯 2025 国 B] 近似回文字符串
Coach_Peter
·
·
题解
题解
看了一眼是我不会滴 DP，还是学了一下题解区的做法（虽然看不懂，自己推了一下，由此诞生了和第一篇题解类似但 dp 定义不同的 DP 题解 hhhh）。
状态定义
我们定义一下 DP 数组：
转移方程
$$
dp[i][0] = dp[i - 2][0] \times 26
$$
含义是在所有 $i-2$ 长度的回文串的基础上，在两边添加一个相同字母。比如说原本是 `bb`，那么我可以在两边添加 `a` 变成 `abba`，添加任意 $26$ 个字母都行，所以是 $\times 26$（这个应该很好理解吧）。
重点还是算 $dp[i][1]$。该状态有两种方式进行转移。
### 第一种
在 $dp[i - 2][1]$ 的字符串集合中的字符串两侧加一个相同字母转移过来。因为长度为 $i-2$ 的地方不是回文串，那么两边增加了一个相同字符后肯定也不可能是回文串，并且我们观察可知两边加上两个相同字符是不会影响 **“并且删除一个字母后其他字母拼接后是回文串”** 的性质的。
举个例子：`abaa` 两边同时加上 `c` 变成 `cabaac`，发现依旧满足性质。
所以：
$$
dp[i][1] \gets dp[i][1] + dp[i - 2][1] \times 26
$$
### 第二种
在 $dp[i - 1][0]$ 的字符串集合中的字符串左右任意一侧加一个字母转移过来。
举个例子：`aba` 右侧加一个 `c` 变成 `abac`；`aba` 左侧加一个 `c` 变成 `caba`，都符合题目要求。
但这时候注意我们不能无脑加任意个字符了（就是不能加全 $26$ 个）。为什么？因为会和第一种方案算出来有重复。
比如说 `abaa` 这个字符串可以由 `ba` 两侧加 `a` 变成，也可以从 `aba` 右侧加 `a` 变成，这样就算重了。所以一边新增加的一个字符不能等于原有的另一边的字符。因此：
$$
dp[i][1] \gets dp[i][1] + dp[i - 1][0] \times 25 \times 2
$$
其中 $\times 25$ 是除了另一端的字符的字符数，$\times 2$ 是有两边。
## 重复修正
难道结束了吗？？？？？这样做完其实还有 **重复**！！！
我们思考一下这个例子：`abab` 可以由 `bab` 左侧加 `a` 变成，也可以由 `aba` 右侧加上 `b` 变成。这种情况发现很少，只有两个字符构成 `ababab` 这样的偶数的时候才会发生。那么这种情况的数量也就 $25 \times 26$，直接减掉就行：
$$
dp[i][1] \gets dp[i][1] - ([i \bmod 2 = 0] \times 25 \times 26)
$$
## 代码
最后代码：
```cpp
// 略（可依上述转移方程实现）