周甄陶

————————————————————————————————————————

思路：分析可知一定是先删去前面和后面然后一端添加字符，所以先n^2处理出前后删减的花费，然后用dp数字达标维护，用dp[i][j][0]表示区间[i,j]向前扩展成回文的最小花费，用dp[i][j][1]表示区间[i,j]向后扩展成回文的最小花费

#include <iostream>

#include<queue>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

#define LL long long

int dp[1005][1005][2];

int a[30],b[30];

char s[1005];

int L[1005],R[1005];

bool dd[1005][1005];

int main()

{

    while(~scanf("%s",s))

    {

        for(int i=0; i<26; i++)

            scanf("%d%d",&a[i],&b[i]);

        int n=strlen(s);

        memset(dd,0,sizeof dd);

        for(int i=1; i<=n; i++)

        {

            dd[i][i]=true;

        }

        for(int i=1; i<n; i++)

        {

            if(s[i-1]==s[i])

                dd[i][i+1]=true;

        }

        for(int j=2; j<n; j++)

            for(int i=1; i<=n; i++)

            {

                if(i+j>n)

                    break;

                dd[i][i+j]=s[i-1]==s[i+j-1]&dd[i+1][i+j-1];

            }

        for(int i=0; i<n; i++)

            dp[i][i][0]=0,dp[i][i][1]=0;

        for(int j=1; j<n; j++)

        {

            for(int i=1; i<=n; i++)

            {

                if(i+j>n) break;

                if(dd[i][i+j])

                {

                    dp[i][i+j][0]= dp[i][i+j][1]=0;

                }

                else

                {

                    dp[i][i+j][0]=dp[i][i+j-1][0]+b[s[i+j-1]-'a'];

                    dp[i][i+j][1]=dp[i+1][i+j][1]+b[s[i-1]-'a'];

               }

            }

        }

        L[0]=0;

        L[1]=a[s[0]-'a'];

        for(int i=2; i<=n; i++)

        {

            L[i]=L[i-1]+a[s[i-1]-'a'];

        }

        R[n+1]=0;

        R[n]=a[s[n-1]-'a'];

        for(int i=n-1; i>0; i--)

        {

            R[i]=R[i+1]+a[s[i-1]-'a'];

        }

        int mn=0x3f3f3f3f;

        for(int i=1; i<=n; i++)

        {

            for(int j=n; j>=i; j--)

            {

                mn=min(mn,L[i-1]+R[j+1]+min(dp[i][j][0],dp[i][j][1]));

            }

        }

        printf("%d\n",mn);

    }

    return 0;

}