题目描述
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
思路：比赛的时候用了Manacher搞，然后dp求解，但是n并不是字符串的长度，所以也不知道是这里的错误还是本身就有错。
现在用O（n^2）的开一个has[L][R]数组，代表[L,R]这个区间有一个回文串，然后dp求解。
dp[i]表示[1,i]区间最大的愉悦度是多少，然后再用一个j往前扫。
dp[i] = max(dp[i], dp[j-1] + a[i-j+1]) (has[j][i] == 1)
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 #define N 5010 5 bool has[N][N]; 6 LL dp[N], a[N]; 7 char s[N]; 8 9 int main() { 10 int t; scanf("%d", &t); 11 while(t--) { 12 int n; scanf("%d", &n); 13 for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); 14 scanf("%s", s + 1); 15 int len = strlen(s + 1); 16 memset(has, 0, sizeof(has)); 17 memset(dp, 0, sizeof(dp)); 18 for(int i = 1; i <= len; i++) { 19 int j = 0; 20 while(1 <= i - j && i + j <= len && s[i-j] == s[i+j]) has[i-j][i+j] = true, j++; 21 j = 0; 22 while(1 <= i - j && i + j + 1 <= len && s[i-j] == s[i+j+1]) has[i-j][i+j+1] = true, j++; 23 } 24 for(int i = 1; i <= len; i++) { 25 dp[i] = dp[i-1]; 26 for(int j = i; i - j + 1 <= n && j; j--) { 27 if(has[j][i]) { 28 dp[i] = max(dp[i], dp[j-1] + a[i-j+1]); 29 } 30 } 31 } 32 printf("%lld ", dp[len]); 33 } 34 return 0; 35 }