1 //Accepted    15880 KB    250 ms 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 const int imax_n = 2005; 7 const int imax_m = 27; 8 const int inf = 100000000; 9 int dp[imax_n][imax_n];10 int addcost[imax_m];11 int deletecost[imax_m];12 int n;13 int m;14 char s[imax_n];15 int min(int a,int b)16 {17     return a<b?a:b;18 }19 void Dp()20 {21     memset(dp,0,sizeof(dp));22     //for (int i=1;i<=n;i++)23     //dp[i][i]=0;24     for (int l=2;l<=n;l++)25     {26         for (int i=1;i<=n;i++)27         {28             int j=i+l-1;29             dp[i][j]=inf;30             if (s[i-1]==s[j-1]) dp[i][j]=dp[i+1][j-1];31             dp[i][j]=min(dp[i][j],dp[i+1][j]+addcost[s[i-1]-‘a‘]);32             dp[i][j]=min(dp[i][j],dp[i+1][j]+deletecost[s[i-1]-‘a‘]);33             dp[i][j]=min(dp[i][j],dp[i][j-1]+addcost[s[j-1]-‘a‘]);34             dp[i][j]=min(dp[i][j],dp[i][j-1]+deletecost[s[j-1]-‘a‘]);35         }36     }37     printf("%d\n",dp[1][n]);38 }39 int main()40 {41     //while (scanf("%d%d",&m,&n)!=EOF)42     {43         scanf("%d%d",&m,&n);44         scanf("%s",s);45         char ss[5];46         memset(addcost,0,sizeof(addcost));47         memset(deletecost,0,sizeof(deletecost));48         for (int i=1;i<=m;i++)49         {50             scanf("%s",ss);51             scanf("%d%d",&addcost[ss[0]-‘a‘],&deletecost[ss[0]-‘a‘]);52         }53         Dp();54     }55     return 0;56 }