2017华南理工华为杯D bx回文
比赛的时候队友过了，补补题XD。题目链接：https://scut.online/p/125（赛后补题）
125. 笔芯回文
题目描述
bx有一个长度一个字符串S，bx可以对其进行若干次操作。
每次操作可以删掉一个长度为k(1≤k≤n)的连续回文子串，bx获得ak的愉悦值。
一个字符串是回文串当且仅当正读和反读都是一样的。例如"a", "aa", "abcba""a","aa","abcba"是回文串，"ab", "abc","aabab""ab","abc","aabab"不是回文串。
字符串删除之后相邻的字符不会合并在一起。
现在，bx想知道他最多能获得多少愉悦值。
输入格式
输入第一行一个整数T，表示数据组数。
对于每组数据，第一行一个整数n。
第二行n个整数，第i个表示ai。
第三行为字符串S。
1≤T≤20
1≤n≤∣S∣≤5000
0≤ai≤1000000000
SS只包括小写字母。
输出格式
对每组数据，输出bx所能获得的最大愉悦值。
样例数据
输入
2
3
1 2 3
aba
3
3 2 1
aba
输出
3
9
备注
题解：
简单的dp题目。用n^2枚举回文串。（ok为第i位到第j为的字符为回文串）
dp为第i位结尾的最大愉悦值。
找动态转移方程：当第j个开始到第i个位回文串的时候 dp = max（dp+a, dp）。j在。
#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;
LL a;
int ok;
LL dp;
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 == s){
ok = 1;
}else break;
}
}
for(int i = 1;i<=len;i++){//判断偶数个时是否为回文串
if(s != s)continue;
ok = 1;
for(int j = 1;;j++){
if( i-j < 1|| i+1+j > len || j*2+2 > n) break;//回文串的长度要小于等于n
if(s == s){
ok = 1;
}else break;
}
}
dp = a;
for(int i=2;i<=len;i++){
dp = max(dp, dp+a);
for(int j = 1;j<i;j++){
if(ok){
dp = max(dp, dp+a);
}
}
}
printf("%lld\n", dp);
}
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 你努力的时候，比你厉害的人也在努力。
页:
[1]