125. 笔芯回文

题目描述

每次操作可以删掉一个长度为 $\leq k \leq n)k(1≤k≤n)的连续回文子串，bxbx获得a_ka?k??的愉悦值。$

一个字符串是回文串当且仅当正读和反读都是一样的。例如

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

现在，

输入格式

输入第一行一个整数

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

第二行 $nn个整数，第ii个表示a_ia?i??。$

第三行为字符串

$\leq T \leq 201≤T≤20$

$\leq n \leq |S| \leq 50001≤n≤∣S∣≤5000$

$\leq a_i \leq 10000000000≤a?i??≤1000000000$

输出格式

对每组数据，输出

样例数据

输入

231 2 3aba33 2 1aba

输出

39

思路：比赛的时候用了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\n", dp[len]);33     }34     return 0;35 }

SCUT 125 ：笔芯回文（DP）

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们