递推预处理 + Manacher

链接：https://www.nowcoder.com/acm/contest/131/D
来源：牛客网

字符串 S 只包含小写英文字母。有四种操作，每次操作你可以选择其中一种：

删除字符串的第一个字母。
删除字符串的最后一个字母。
在字符串的头部添加任意一个你想要的字母。
在字符串的尾部添加任意一个你想要的字母。

删除一个第 i 种英文字母需要的花费是 A_i，添加一个第 i 种英文字母的花费是 B_i。
请问将字符串 S 变成回文串需要的最小花费是多少？

输入描述:

第一行输入一个字符串 S。
接下来 26 行，每行输入两个正整数 A

和 B

，表示删除一个第 i 种字符所需的花费以及添加一个第 i 种字符所需的花费。

1≤ |S| ≤ 10

⁵

且字符串 S 中只包含小写英文字母 1≤ A

,B

≤ 10⁹.

输出描述:

输出一个正整数，表示把字符串 S 变成一个回文串的最小花费。

输入

输出

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
",l, r, ans);
    }
    printf("%lld
", ans);
    return 0;
}

东北日出西边雨道是无情却有情