最便宜的回文

跟踪所有的奶牛可能是一个棘手的任务，所以农夫约翰已经安装了一个自动化系统。他在每只牛上安装了一个电子ID标签，系统将在扫描仪通过奶牛时读取。每个ID标签的内容当前是从N（1≤N≤26）个不同符号（即小写罗马字母表）的字母表中绘出的长度为M（1≤M≤2000）个字符的单个字符串。

奶牛作为他们的调皮生物，有时试图通过向后走向欺骗系统。而ID为“abcba”的奶牛，无论她走哪一个方向，都会读取相同的奶牛，ID为“abcb”的奶牛可以注册为两个不同的ID（“abcb”和“bcba”）。

FJ想改变奶牛的ID标签，所以他们读取同样的东西，无论牛走哪边方向。例如，可以通过在末尾添加“a”来更改“abcb”，以形成“abcba”，以便ID是回文（读取相同的向前和向后）。将ID更改为回文的其他一些方法包括将三个字母“bcb”添加到开头以产生ID“bcbabcb”或删除字母“a”以产生ID“bcb”。可以在字符串中的任何位置添加或删除字符串，生成比原始字符串更长或更短的字符串。

不幸的是，由于ID标签是电子的，所以每个字符的插入或删除都有成本（0≤成本≤10,000），这取决于要添加或删除的字符值的准确性。鉴于牛的ID标签的内容和插入或删除每个字母的字符的成本，找到更改ID标签的最低成本，以满足FJ的要求。空的ID标签被认为是满足阅读相同的向前和向后的要求。只有带有相关费用的字母可以添加到字符串。

输入

行1：两个空格分隔的整数：N和M
行2：这行直接包含构成初始ID字符串的M个字符
行3 .. N + 2：每行包含三个空格分隔的实体：输入字母的字符和两个整数，分别是添加和删除该字符的成本。

输出

第1行：单行，单个整数是更改给定名称标签的最低成本。

样例输入

3 4
abcb
a 1000 1100
b 350 700
c 200 800

样例输出

900

提示

如果我们在末尾插入一个“a”来获取“abcba”，那么费用将是1000.如果我们从头开始删除“a”来获取“bcb”，那么费用将是1100.如果我们插入“bcb” 在弦的开始，成本将是350 + 200 + 350 = 900，这是最小的。

分析

这个问题的主要思想是将一个不是回文的字符串转换成一个字符串。 每个角色的变化都有一个价格，（改变方法是增加或减少），基于动态规划的理论，我们可以知道，实际上增加字符和字符来减少效果是一样的，因为本文给了我们一个 选择两个价格，我们会选择一个。 较少，改变字符串，所以它成为回文。 所以，我们不必付出代价，当我们存储时，我们只存储较小的。 扫描时，只要使用比较，前后角色，谁更有利？

代码

#include<iostream> 
#include<algorithm> 
#define inf 1e8 
using namespace std;  
int dp[2020][2020];  
int main()  
{  int n,m,vis[30];  scanf("%d%d",&n,&m);char a[2020];  scanf("%s",a); //Input stringint x,y;  char z;  for(int i=0;i<n;i++)  {  cin>>z>>x>>y;  vis[z-'a']=min(x,y); //Take the smallest price}  /*if(m==1) //These two can be removed, but with the words, time will be much less{ printf("0\n"); continue; } if(m==2) { dp[0][1]=min(vis[a[0]-'a'],vis[a[1]-'a']); printf("%d\n",dp[0][1]); continue; }*/  for(int j=1;j<m;j++)  {  for(int i=j-1;i>=0;i--)  {  dp[i][j]=inf; //Assign infinityif(a[i]==a[j])  dp[i][j]=dp[i+1][j-1];  //Lean against the centerelse {  dp[i][j]=min(dp[i+1][j]+vis[a[i]-'a'],dp[i][j-1]+vis[a[j]-'a']);//Modify the cheapest way}  }  }  printf("%d\n",dp[0][m-1]);  //The optimal solution from 0 to M-1 (as from 0)return 0;  
}