题目大意
给定一个字符串，要求你通过插入和删除操作把它变为回文串，对于每个字符的插入和删除都有一个花费，问你把字符串变为回文串最少需要多少花费
题解
看懂题立马YY了个方程，敲完就交了，然后就A了，爽歪歪，哈哈~~~
dp[i][j]表示把s[i..j]变为回文的最小花费，设cost[0][ch-‘a’]和cost[1][ch-‘a’]分别为插入字符ch和删除字符ch的花费
如果s[i]==s[j]那么dp[i][j]=dp[i+1][j-1],否则dp[i][j]=min(dp[i+1][j]+min(cost[0][s[i]-‘a’],cost[1][s[i]-‘a’]),dp[i][j-1]+min(cost[0][s[j]-‘a’],cost[1][s[j]-‘a’]))
用滚动数组优化了下空间O(∩_∩)O~~
代码：
#include<stdio.h>
#include<string.h>
#define MAXN 2005
int dp[2][MAXN],cost[30];
char s[MAXN];
int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
scanf("%s",s+1);
for(int i=0; i<m; i++)
{
char ch;
int a,b;
getchar();
scanf("%c",&ch);
scanf("%d%d",&a,&b);
cost[ch-'a']=min(a,b);
}
for(int i=0; i<=n; i++)
{
dp[0][i]=0;
dp[1][i]=0;
}
for(int i=n; i>=1; i--)
for(int j=i; j<=n; j++)
if(s[i]==s[j])
dp[i&1][j]=dp[(i+1)&1][j-1];
else
dp[i&1][j]=min(dp[(i+1)&1][j]+cost[s[i]-'a'],dp[i&1][j-1]+cost[s[j]-'a']);
printf("%d\n",dp[1][n]);
}
return 0;
}