题解

思路

小范围可以直接枚举每次删除的回文子串；中等范围把当前剩余字符串作为状态进行记忆化。满分范围使用区间动态规划，关键是描述“删除一部分字符后只留下一个回文串”的最优得分。

做法

定义：

• $Full[l][r]$：把原串区间 $[l,r]$ 完全删除的最大得分；
• $Best[l][r]$：只在区间内操作、允许留下任意字符的最大得分；
• $T[l][r][k]$：在区间内操作后只留下一个长度为 $k$ 的回文串时，删除部分获得的最大得分。

计算 $T$ 时，最终回文的第一个保留字符可能不在 $l$，此时其左侧前缀必须完全删除；最后一个保留字符也可不在 $r$，此时右侧后缀必须完全删除。若 $s_l=s_r$，还可以同时保留两端并转移到 $T[l+1][r-1][k-2]$。长度为 1 时枚举唯一保留字符。

完全删除区间的最后一次操作一定删除留下的整个回文，因此

$$Full[l][r]=\max_{a_k\ne-1}\{T[l][r][k]+a_k\}.$$

若最优方案没有完全删除区间，则存在一个分割点，使所有删除操作分别位于两侧。因此

$$Best[l][r]=\max\left(0,Full[l][r],\max_m Best[l][m]+Best[m+1][r]\right).$$

按区间长度递增计算即可。

复杂度

时间复杂度为 $O(l^4)$，空间复杂度为 $O(l^3)$。