链接：https://www.nowcoder.com/acm/contest/131/D
来源：牛客网
第一行输入一个字符串 S。
接下来 26 行，每行输入两个正整数 A
i
和 B
i
，表示删除一个第 i 种字符所需的花费以及添加一个第 i 种字符所需的花费。
1≤ |S| ≤ 10
5
且字符串 S 中只包含小写英文字母 1≤ A
i
,B
i
≤ 109.
输出一个正整数，表示把字符串 S 变成一个回文串的最小花费。
jelly 1000 1100 350 700 200 800 2000 2000 2000 432 2000 2000 2000 2000 2000 2000 2000 2000 20 2000 2000 2000 350 35 200 800 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 15 2000 2000 2000
105
题意 ： 给你一个字符串，每次只能在两端操作，增加一个字符或删掉一个字符，将其变成最长回文串
思路分析：一个马拉车可以预处理处理以每个位置为中心开始的最长回文子串，然后接下来的操作就是将一侧全部去掉，另一侧选择性的补齐一部分即可，每次补齐操作都是针对到两个边界的区间的，因此可以直接预处理处理
代码示例：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 1e5+5;
char s[maxn], now[maxn*2];
ll a[30], b[30];
ll len;
ll qa[maxn], qb[maxn], ha[maxn], hb[maxn];
ll qs[maxn], hs[maxn];
ll p[2*maxn];
void init() {
for(ll i = 1; i <= len; i++) qa[i] = qa[i-1]+a[s[i]-‘a‘];
for(ll i = 1; i <= len; i++) qb[i] = qb[i-1]+b[s[i]-‘a‘];
for(ll i = len; i >= 1; i--) ha[i] = ha[i+1]+a[s[i]-‘a‘];
for(ll i = len; i >= 1; i--) hb[i] = hb[i+1]+b[s[i]-‘a‘];
ll pos = 0;
for(ll i = 1; i <= len; i++){
if (qa[i] < qa[pos]+qb[i]-qb[pos]){
pos = i;
qs[i] = qa[i];
}
else qs[i] = qa[pos]+qb[i]-qb[pos];
}
pos = len+1;
for(ll i = len; i >= 1; i--){
if (ha[i] < ha[pos]+hb[i]-hb[pos]){
pos = i;
hs[i] = ha[i];
}
else hs[i] = ha[pos]+hb[i]-hb[pos];
}
}
void Manacher()
{
for (ll i=1;i<=len;i++) now[2*i-1]=‘%‘,now[2*i]=s[i];
now[len=len*2+1]=‘%‘;
ll pos=0,R=0;
for (ll i=1;i<=len;i++)
{
if (i<R) p[i]=min(p[2*pos-i],R-i); else p[i]=1;
while (1<=i-p[i]&&i+p[i]<=len&&now[i-p[i]]==now[i+p[i]]) p[i]++;
if (i+p[i]>R) {pos=i;R=i+p[i];}
}
}
int main () {
scanf("%s", s+1);
len = strlen(s+1);
for(ll i = 0; i < 26; i++) scanf("%lld%lld", &a[i], &b[i]);
init();
Manacher();
ll ans = (1ll)<<60;
ll l, r;
for(ll i = 1; i <= len; i++){
p[i]--;
if (i%2){
ll ff = p[i]/2;
l = i/2-ff, r = i/2+ff+1;
}
else {
ll ff = p[i]/2;
l = i/2-ff-1, r = i/2+ff+1;
}
ans = min(ans, qa[l]+hs[r]);
ans = min(ans, ha[r]+qs[l]);
//printf("%lld %lld %lld\n",l, r, ans);
}
printf("%lld\n", ans);
return 0;
}
原文：https://www.cnblogs.com/ccut-ry/p/9365882.html