题解：CF150D Mission Impassable
A6n6d6y6
·
·
题解
题意
有一个字符串 s，每次操作可以删掉长度为 i 的回文子串并获得 v_i 的分数。
特别地，v_i=−1 代表不能删除长度为 i 的串。
操作完之后将删除位置前后字符串拼接起来。
重复操作若干次，问最多能获得多少分数。
思路
套路地，尝试区间 DP，设 $h_{l,r}$ 表示将 $[l,r]$ 操作若干次后，能获得的最大分数。
那么有 $h_{l,r}=\max\{0,h_{l,p}+h_{q,r}\}$，其中 $l\le p\lt q\le r$，但是并不知道初始值。
不妨设 $f_{l,r}$ 为将 $[l,r]$ **全部删除**后能获得的最大分数，可以证明，这一定能做到。
此时 $h_{l,r}$ 的**初始值**就是 $f_{l,r}$，即 $h_{l,r}=\max\{0,f_{l,r},h_{l,p}+h_{q,r}\}$，其中 $l\le p\lt q\le r$。
考虑转移 $f_{l,r}$，显然有 $f_{l,r}=\max\{f_{l,p}+f_{p+1,r}\}$，其中 $l\le p\lt r$，问题仍在。
如何处理**回文串**的转移？考虑再设 $g_{l,r,k}$ 表示将 $[l,r]$ **删到只剩**一个长度为 $k$ 的**回文串**后获得的最大分数。
那么 $f_{l,r}$ 就可以看作 $g_{l,r,0}$，即为 $\max\{g_{l,r,k}+a_k\}$，其中 $1\le k\le r-l+1$（不过下面仍然会区分 $f_{l,r}$ 和 $g_{l,r,0}$）。
如果 $s_l=s_r$，那么 $g_{l,r,k}$ 可以从 $g_{l+1,r-1,k-2}$ 转移；也可以枚举断点，分讨回文串来自断点左右侧从而转移。
综上：
$f$ 的转移式为：$f_{l,r}=\max\{g_{l,r,k}+a_k,f_{l,p}+f_{p+1,r}\}$，其中 $1\le k\le r-l+1,l\le p\lt r$。
$g$ 的转移式为：$g_{l,r,k}=\max\{f_{l,p}+g_{p+1,r,k},g_{l,p,k}+f_{p+1,r},[k\ge 2\land s_l=s_r]g_{l+1,r-1,k-2}\}$，其中 $l\le p\lt r$。
$h$ 的转移式为：$h_{l,r}=\max\{0,f_{l,r},h_{l,p}+h_{q,r}\}$，其中 $l\le p\lt q\le r$。
初始值：$f_{i,i}=g_{i,i,0}=v_1$，$g_{i,i,1}=0$，为了方便处理偶回文，令 $f_{i+1,i}=0$，其中 $0\le i\le n$。
答案即为 $h_{1,n}$，时间复杂度为 $\mathcal{O}(n^4)$ ，实测可过。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1.5e2+10,inf=0x3f3f3f3f;
int v[maxn],f[maxn][maxn],g[maxn][maxn][maxn],h[maxn][maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++){
int w;cin>>w;
v[i]=(~w?w:-inf);
}
string s;cin>>s;s=' '+s;
memset(f,-inf,sizeof f);
memset(g,-inf,sizeof g);
memset(h,-inf,sizeof h);
for(int i=1;i<=n;i++)
h[i][i]=max(f[i][i]=g[i][i][0]=v[1],g[i][i][1]=0);
for(int i=0;i<=n;i++)
h[i+1][i]=f[i+1][i]=g[i+1][i][0]=0;
for(int len=2;len<=n;len++){
for(int l=1,r=len;r<=n;l++,r++){
for(int k=1;k<=len;k++){
if(k>=2&&s[l]==s[r])
g[l][r][k]=max(g[l][r][k],g[l+1][r-1][k-2]);
for(int p=l;p!=r;p++){
g[l][r][k]=max(g[l][r][k],f[l][p]+g[p+1][r][k]);
g[l][r][k]=max(g[l][r][k],g[l][p][k]+f[p+1][r]);
}
f[l][r]=max(f[l][r],g[l][r][k]+v[k]);
}
for(int p=l;p!=r;p++)
f[l][r]=max(f[l][r],f[l][p]+f[p+1][r]);
h[l][r]=max(0,f[l][r]);
g[l][r][0]=max(g[l][r][0],f[l][r]);
for(int p=l;p<=r;p++)
for(int q=p+1;q<=r;q++)
h[l][r]=max(h[l][r],h[l][p]+h[q][r]);
}
}
cout<<h[1][n];
return 0;
}
```