题目链接： https://scut.online/p/125
题目描述
bxbx有一个长度一个字符串SS，bxbx可以对其进行若干次操作。
每次操作可以删掉一个长度为k(1 \leq k \leq n)k(1≤k≤n)的连续回文子串，bxbx获得a_kak的愉悦值。
一个字符串是回文串当且仅当正读和反读都是一样的。例如"a", "aa", "abcba""a","aa","abcba"是回文串，"ab", "abc","aabab""ab","abc","aabab"不是回文串。
字符串删除之后相邻的字符不会合并在一起。
现在，bxbx想知道他最多能获得多少愉悦值。
输入格式
输入第一行一个整数TT，表示数据组数。
对于每组数据，第一行一个整数nn。
第二行nn个整数，第ii个表示a_iai。
第三行为字符串SS。
1 \leq T \leq 201≤T≤20
1 \leq n \leq |S| \leq 50001≤n≤∣S∣≤5000
0 \leq a_i \leq 10000000000≤ai≤1000000000
SS只包括小写字母。
输出格式
对每组数据，输出bxbx所能获得的最大愉悦值。
样例数据
输入
2
3
1 2 3
aba
3
3 2 1
aba
输出
3
9
题解：
1.ok[l][r]代表区间l~r的子串是否为回文串，O(n^2)预处理。
2. dp[i]代表删除前i个字符的最大价值， 状态转移方程为：if(ok[j][i]) dp[i] = max(dp[i],dp[j-1]+a[i-j+1]);
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+;
const int maxn = +; char s[maxn];
LL a[maxn], dp[maxn];
bool ok[maxn][maxn]; int n, len; void init()
{
ms(ok,);
ms(dp,); for(int i = ; i<=len; i++)
{
int l = i, r = i;
while(l>= && r<=len && (r-l+)<=n && s[l]==s[r])
ok[l--][r++] = ;
} for(int i = ; i<=len; i++)
{
int l = i, r = i+;
while(l>= && r<=len && (r-l+)<=n && s[l]==s[r])
ok[l--][r++] = ;
}
} void solve()
{
for(int i = ; i<=len; i++)
for(int j = ; j<=i; j++)
{
if(ok[j][i])
dp[i] = max(dp[i],dp[j-]+a[i-j+]);
} printf("%lld\n",dp[len]);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = ; i<=n; i++)
scanf("%lld",&a[i]); scanf("%s", s+);
len = strlen(s+); init();
solve();
}
return ;
}