题目描述
wzy 在玩一种很新的祖玛。
给定一个仅包含 小写字母 的字符串 sss , sss 由 mmm 个不同的小写字母组成，每个字母代表一种小球，在消去时会获得 相应 的分数：
- 两个及以上 相同的小球相碰就会消失（在发射小球前因为无相碰，所以有两个及以上小球相邻也不会消失）。
- 每次碰撞后，消失获得的分数为：对应小球分数×消失个数。
你可以进行 一次 操作：
发射一个任意小球于 sss 的任意位置(也可以是 头和尾 )。
发射小球后，按照规则进行，直到不能碰撞为止。
请你求出经过一次操作后取得的 最大分数 。
输入描述:
第一行包含两个整数 n，m(1≤n≤105,1≤m≤26)n，m(1\le n \le 10^5,1\le m\le 26)n，m(1≤n≤105,1≤m≤26) - 表示字符串长度 和 字符集大小。
第二行包含一个长度为 nnn 字符串 sss。
接下来 mmm 行，每行包含 c,k(′a′≤c≤c,k('a'\le c\lec,k(′a′≤c≤ ′z′,1≤k≤109)'z',1\le k\le10^9)′z′,1≤k≤109) - 表示每消除一个字母 ccc 有 kkk 分。
保证：字符串 sss 中的字母必定在给定字符集中出现。
输出描述:
输出一次操作能获得的最高得分。
示例1
输入
复制6 3 abccba a 1 b 2 c 3
6 3 abccba a 1 b 2 c 3
输出
复制15
15
说明
样例一的解释：
最终将全部字母消除，得分为 3×3+2×2+2×1=153×3+2×2+2×1 = 153×3+2×2+2×1=15 即为最大
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s,s2;
long long score[30];
long long ans;
int p[300010];
long long pre[100010];
void mlc(){
int mid,mr=0;
for(int i=1;i<s2.size();i++){
if(i<mr) p[i]=min(p[mid*2-i],mr-i);
else p[i]=1;
while(s2[i-p[i]]==s2[i+p[i]]) p[i]++;
if(i+p[i]>mr){
mr=i+p[i];
mid=i;
}
}
}
int main(){
scanf("%d%d",&n,&m);
cin>>s;
for(int i=1;i<=m;i++){
char c;
long long num;
cin>>c;
scanf("%lld",&num);
score[c-'a']=num;
}
s2+='&';
s2+=s[0];
pre[1]=score[s2[1]-'a'];
for(int i=1,j=1;i<s.size();i++){
if(s[i]!=s[i-1]) {
s2+=s[i];
j++;
pre[j]=pre[j-1]+score[s[i]-'a'];//s2的前缀和
}
else{
pre[j]+=score[s[i]-'a'];
}
}
s2+='^';
//将s中连续出现的某个字母合并成只有一个，最终形成s2，这样的s2的回文串只能为奇数，因此直接头和尾加一个不同的字符即可，不用再加‘#’
mlc();
for(int i=1;i<s2.size();i++){
long long res;
res=pre[i+p[i]-1]-pre[i-p[i]]+score[s2[i]-'a']; //以i为中心，左右分别延长p[i]-1的回文串
ans=max(ans,res);
}
cout<<ans;
}
