低价回文_牛客博客

题目链接：http://acm.ocrosoft.com/problem.php?cid=1629&pid=52

题目描述：

追踪每头奶牛的去向是一件棘手的任务，为此农夫约翰安装了一套自动系统。他在每头牛身上安装了一个电子身份标签，当奶牛通过扫描器的时候，系统可以读取奶牛的身份信息。目前，每个身份都是由一个字符串组成的，长度为M (1≤M≤2000)，所有的字符都取自小写的罗马字母。

奶牛们都是顽皮的动物，有时她们会在通过扫描器的时候倒着走，这样一个原来身份为abcb的奶牛就可能有两个不同的身份了（abcb和bcba），而如果身份是abcba的话就不会有这个问题了。

约翰想改变奶牛们的身份，使他们不管怎么走读起来都一样。比如说，abcb可以在最后加个a，变成回文abcba；也可以在前面加上bcb，变成回文bcbabcb；或者去除字母a，保留的bcb也是一条回文。总之，约翰可以在任意位置删除或插入一些字符使原字符串变成回文。

不巧的是，身份标签是电子做的，每增加或删除一个字母都要付出相应的费用（0≤代价≤10000）。给定一头奶牛的身份标签和增加或删除相关字母的费用，找出把原来字符串变成回文的最小费用。注意空字符串也是回文。

输入

第一行：两个用空格分开的整数：N和M

第二行：一个长度恰好为M的字符串，代表初始的身份标签

第三行到第N+2行：每行为一个用空格分开的三元组：其中包括一个字符和两个整数，分别表示增加或删除这个字符的费用

输出

第一行：只有一个整数，表示改造这个身份标签的最小费用

样例输入:

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

样例输出:

思路：

这个问题的主要思想是将一个不是回文的字符串转换成一个字符串。每个字符的变化都有一个价格，如果 a[i+1,j]已经是回文，那么删掉 a[i]与在 a[j,j+1] 中间插入 a[i]两个操作是等价的，即 v[k−’a’]=min{insert[k],delete[k]}.

如果a[i-1]==a[j+1]，那么显然有dp[i-1][j+1]=min(dp[i-1][j+1],dp[i][j]);

dp[i-1][j]=min(dp[i-1][j],dp[i][j]+v[s[i-1]-‘a’]);

dp[i][j+1]=min(dp[i][j+1],dp[i][j]+v[s[j+1]-‘a’]);

代码：

#include<bits/stdc++.h>
#define inf 1e8
using namespace std;

int dp[2020][2020];//将a[i,j]变成回文字符串的最小代价

int main()
{
    int n,m,x,y,v[30];
    char z,a[2020];
    scanf("%d%d",&n,&m);
    scanf("%s",a);
    for(int i=0;i<n;i++)
    {
        cin>>z>>x>>y;
        v[z-'a']=min(x,y);//改变字符z所用的价格
    }
    for(int j=1;j<m;j++)
    {
        for(int i=j-1;i>=0;i--)
        {
            dp[i][j]=inf;
            if(a[i]==a[j])
                dp[i][j]=dp[i+1][j-1];
            else
                dp[i][j]=min(dp[i+1][j]+v[a[i]-'a'],dp[i][j-1]+v[a[j]-'a']);
        }
    }
    printf("%d\n",dp[0][m-1]);
    return 0;
}