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所能获得的最大愉悦值。

样例数据

输入

输出

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)

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 #define N 5010

 bool has[N][N];

 LL dp[N], a[N];

 char s[N];

 int main() {

     int t; scanf("%d", &t);

     while(t--) {

         int n; scanf("%d", &n);

         for(int i = ; i <= n; i++) scanf("%lld", &a[i]);

         scanf("%s", s + );

         int len = strlen(s + );

         memset(has, , sizeof(has));

         memset(dp, , sizeof(dp));

         for(int i = ; i <= len; i++) {

             int j = ;

             while( <= i - j && i + j <= len && s[i-j] == s[i+j]) has[i-j][i+j] = true, j++;

             j = ;

             while( <= i - j && i + j +  <= len && s[i-j] == s[i+j+]) has[i-j][i+j+] = true, j++;

         }

         for(int i = ; i <= len; i++) {

             dp[i] = dp[i-];

             for(int j = i; i - j +  <= n && j; j--) {

                 if(has[j][i]) {

                     dp[i] = max(dp[i], dp[j-] + a[i-j+]);

                 }

             }

         }

         printf("%lld\n", dp[len]);

     }

     return ;

 }

巴特西

SCUT 125 ：笔芯回文（DP）

125. 笔芯回文

题目描述

输入格式

输出格式

样例数据

最新文章

热门文章