C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 3816K, 提交时间: 2018-07-06 20:59:34

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100005;

char s[N];
char c[2*N];
ll a[26],b[26];

ll f[N][2];
ll L[N];
int p[2*N];
ll solve(int l)
{
    f[0][0]=f[0][1]=0;
    for (int i=1;i<=l;i++)
    {
        f[i][0]=f[i-1][0]+a[s[i]-'a'];
        f[i][1]=min(f[i-1][0],f[i-1][1])+b[s[i]-'a'];
        L[i]=min(f[i][0],f[i][1]);
    }
    
    c[0]='('; c[1]='#';
    int len=1;
    for (int i=1;i<=l;i++) c[++len]=s[i],c[++len]='#';
    c[++len]=')';
    int mx=0,id=0;
    for (int i=1;i<len;i++)
    {
        if (i<=mx) p[i]=min(mx-i,p[id*2-i]);
        else p[i]=0;
        while(c[i+p[i]+1]==c[i-p[i]-1]) p[i]++;
        if (i+p[i]>mx) mx=i+p[i],id=i;
    }
    ll ret=1e18;
    for (int i=2;i<len-1;i++)
    {
        int r=(i+p[i])/2;
        ret=min(ret,L[r-p[i]]+f[l][0]-f[r][0]);
    }
    return ret;
}
int main()
{
    scanf("%s",s+1);
    for (int i=0;i<26;i++) scanf("%lld%lld",&a[i],&b[i]);
    int len=strlen(s+1);
    ll ans=solve(len);
    reverse(s+1,s+len+1);
    ans=min(ans,solve(len));
    printf("%lld\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 4708K, 提交时间: 2018-07-10 13:59:00

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+88;
int len,a[26],b[26],h[N<<1|1];
long long f[N],g[N],pre[N],suf[N];
char buf[N],str[N<<1|1];
int main(){
	scanf("%s",buf+1);
	len=strlen(buf+1);
	for(int i=0;i<26;++i) scanf("%d%d",a+i,b+i);
	str[0]='$';
	for(int i=1;i<=len;++i) {
		int o=buf[i]-'a';
		f[i]=f[i-1]+a[o];//删除前缀和 
		g[i]=g[i-1]+b[o];//添加前缀和 
		str[i*2-1]=buf[i];
		str[i*2]='#';
	}
	long long mx=0;
	for(int i=1;i<=len;++i){
		mx=min(mx,f[i]-g[i]);
		pre[i]=g[i]+mx;
	}
	mx=0;
	for(int i=len;i>=1;--i){
		mx=min(mx,f[len]-f[i-1]+g[i-1]-g[len]);
		suf[i]=g[len]-g[i-1]+mx;
	} 
	long long ans=~0ull>>1;
	for(int i=1,mx=0,id;i<len*2;++i) {
		h[i]=i<mx?min(h[2*id-i],mx-i):1;
		for(;str[i-h[i]]==str[i+h[i]];++h[i]);
		if(mx<i+h[i]) {
			mx=i+h[i];
			id=i;
		}
		int L=(i-h[i]+1)/2+1,R=(i+h[i])/2;
		if(L<=R) {
			ans=min(ans,f[L-1]+suf[R+1]);
			ans=min(ans,f[len]-f[R]+pre[L-1]);
		}
	}
	printf("%lld\n",ans);
}