2017华南理工华为杯D bx回文

xian123

　　比赛的时候队友过了，补补题XD。
　　题目链接：https://scut.online/p/125（赛后补题）











125. 笔芯回文















题目描述


　　bx有一个长度一个字符串S，bx可以对其进行若干次操作。
　　每次操作可以删掉一个长度为k(1≤k≤n)的连续回文子串，bx获得a​k​​的愉悦值。
　　一个字符串是回文串当且仅当正读和反读都是一样的。例如"a", "aa", "abcba""a","aa","abcba"是回文串，"ab", "abc","aabab""ab","abc","aabab"不是回文串。
　　字符串删除之后相邻的字符不会合并在一起。
　　现在，bx想知道他最多能获得多少愉悦值。



输入格式


　　输入第一行一个整数T，表示数据组数。
　　对于每组数据，第一行一个整数n。
　　第二行n个整数，第i个表示a​i​​。
　　第三行为字符串S。
　　1≤T≤20
　　1≤n≤∣S∣≤5000
　　0≤a​i​​≤1000000000
　　SS只包括小写字母。


输出格式


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


样例数据


　　输入

2
3
1 2 3
aba
3
3 2 1
aba
　　输出

3
9


备注
　　题解：
　　简单的dp题目。用n^2枚举回文串。（ok[j]为第i位到第j为的字符为回文串）
　　dp为第i位结尾的最大愉悦值。
　　找动态转移方程：当第j个开始到第i个位回文串的时候 dp = max（dp[j-1]+a[i到j的距离], dp）。j在[1, i-1]。





#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ms(a, b)  memset((a), (b), sizeof(a))
//#define LOCAL
#define eps 0.0000001
typedef long long LL;
const int inf = 0x3f3f3f3f;
const LL INF = 0x7fffffff;
const int maxn = 5000+10;
const int mod = 1000000007;
char s[maxn];
LL a[maxn];
int ok[maxn][maxn];
LL dp[maxn];
void init()
{
     ms(s, 0);
     ms(ok, 0);
     ms(dp, 0);
}
void solve()
{
     int n;
     scanf("%d", &n);
     for(int i = 1;i<=n;i++)     scanf("%lld", &a);
     scanf("%s", s+1);
     int len = strlen(s+1);
//    printf("%d\n", len);
     for(int i=1;i<=len;i++){//判断奇数时逝世后为回文串
         ok = 1;
         for(int j = 1;;j++){
             if(( j*2 + 1) > n || i-j <1 || i+j > len )  break;//回文串的长度要小于等于n
             if(s[i-j] == s[i+j]){
                 ok[i-j][i+j] = 1;
             }else    break;
         }
     }
     for(int i = 1;i<=len;i++){//判断偶数个时是否为回文串
         if(s != s[i+1])  continue;
         ok[i+1] = 1;
         for(int j = 1;;j++){
             if( i-j < 1|| i+1+j > len || j*2+2 > n)   break;//回文串的长度要小于等于n
             if(s[i-j] == s[i+1+j]){
                 ok[i-j][i+1+j] = 1;
             }else    break;
         }
     }
     dp[1] = a[1];
     for(int i=2;i<=len;i++){
         dp = max(dp, dp[i-1]+a[1]);
         for(int j = 1;j<i;j++){
             if(ok[j]){
                 dp = max(dp, dp[j-1]+a[i-j+1]);
             }
         }
     }
     printf("%lld\n", dp[len]);
}
int main() {
#ifdef LOCAL
     freopen("input.txt", "r", stdin);
//      freopen("output.txt", "w", stdout);
#endif // LOCAL
//    ios::sync_with_stdio(0);
//    cin.tie();
     int T;
     scanf("%d", &T);
     while(T--){
         init();
         solve();
     }
     return 0;
}
View Code　　你努力的时候，比你厉害的人也在努力。