bx回文

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 577    Accepted Submission(s): 113

Problem Description
bx有一个长度一个字符串S，bx可以对其进行若干次操作。

每次操作可以删掉一个长度为k(1 <= k <= n)的连续回文子串，bx获得 ak的愉悦值。

一个字符串是回文串当且仅当正读和反读都是一样的。例如"a"，"aa"，”abcba”是回文串，"ab","abc","aabab"不是回文串。

字符串删除之后相邻的字符不会合并在一起。

现在，bx想知道他最多能获得多少愉悦值。
 

Input
输入第一行一个整数T,表示数据组数。

对于每组数据，第一行一个整数n。

第二行n个整数，第i个表示 ai。

第三行为字符串S。

1 <= T <= 20
1 <= n <= |S| < 5000 
0 <=  ai < 1000000000 
S只包括小写字母。
 

Output
对每组数据，输出bx所能获得的最大愉悦值。
 

Sample Input
2 3 1 2 3 aba 3 3 2 1 aba
 

Sample Output
3 9


先o(n2)预处理 得到每段区间内是否是回文串，然后o(n)查询更新愉悦值


#include <bits/stdc++.h>  
using namespace std;  
typedef long long LL;   
const int maxn = 5000+5;  
  
char s[maxn];  
LL a[maxn], dp[maxn];  
bool ok[maxn][maxn];  
  
int n, len;  
  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%d",&n);  
        for(int i = 1; i<=n; i++)  
            scanf("%lld",&a[i]);  
  
        scanf("%s", s+1); 
        len = strlen(s+1);  
//        cout<<len<<endl;
      
        memset(ok,0,sizeof(ok));  
        memset(dp,0,sizeof(dp));  
      
        for(int i = 1; i<=len; i++)  
        {  
            int l = i, r = i;  
            while(l>=1 && r<=len && (r-l+1)<=n && s[l]==s[r])  
                ok[l--][r++] = 1;  
        }  
      
        for(int i = 1; i<=len; i++)  
        {  
            int l = i, r = i+1;  
            while(l>=1 && r<=len && (r-l+1)<=n && s[l]==s[r])  
                ok[l--][r++] = 1;  
        }  
        for(int i = 1; i<=len; i++)  
            for(int j = 1; j<=i; j++){  
                if(ok[j][i])  
                    dp[i] = max(dp[i],dp[j-1]+a[i-j+1]);  
            }  
        printf("%lld\n",dp[len]); 
    }
    return 0;  
}