POJ3280 Cheapest Palindrome

一、题目内容

【题目描述】

给你长度为m的字符串，其中有n种字符，每种字符都有两个值，分别是插入这个字符的代价，删除这个字符的代价，让你求将原先给出的那串字符变成一个回文串的最小代价。

【输入格式】

第一行n,m;
第二行一个字符串
接下来n行一个字母，两个整数用空格隔开，分别代表增加和删除的代价

【输出格式】

一个整数，最小代价

【输入样例】

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

【输出样例】

0

【说明】

If we insert an “a” on the end to get “abcba”, the cost would be 1000. If we delete the “a” on the beginning to get “bcb”, the cost would be 1100. If we insert “bcb” at the begining of the string, the cost would be 350 + 200 + 350 = 900, which is the minimum.

【测试网站】

poj3280

二、题目分析

dp[i][j]代表区间i到区间j成为回文串的最小代价，那么对于dp[i][j]有三种情况：
1、dp[i+1][j]表示区间i到区间j已经是回文串了的最小代价，那么对于s[i]这个字母，我们有两种操作，删除与添加，对应有两种代价，dp[i+1][j]+add[s[i]],dp[i+1][j]+del[s[i]]，取这两种代价的最小值；
2、dp[i][j-1]表示区间i到区间j-1已经是回文串了的最小代价，那么对于s[j]这个字母，同样有两种操作，dp[i][j-1]+add[s[j]],dp[i][j-1]+del[s[j]]，取最小值
3、若是s[i]==s[j]，dp[i+1][j-1]表示区间i+1到区间j-1已经是回文串的最小代价，那么对于这种情况，我们考虑dp[i][j]与dp[i+1][j-1]的大小
然后dp[i][j]取上面这些情况的最小值

三、代码示例

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;
const int maxn = 2000 + 10;
int n,m;
int a[26],b[26],dp[maxn][maxn];
string str;

int main()
{
  scanf("%d%d",&n,&m);
  cin >> str;
  for(int i = 1; i <= n; i++)
  {
    getchar();
    char c;
    int x,y;
    scanf("%c%d%d",&c,&x,&y);
    a[c-'a'] = x; b[c-'a'] = y;
  }
  for(int i = m-1; i >= 0; i--)
   {
     dp[i][i] = 0;
     for(int j = i+1; j <= m; j++)
   {
     dp[i][j] = 0x3f3f3f3f;
     if(str[i] == str[j])
     {  if(i == j-1) dp[i][j] = 0;
        else dp[i][j] = dp[i+1][j-1];
     }
     dp[i][j] = min(dp[i][j],dp[i+1][j] + min(a[str[i]-'a'], b[str[i]-'a']));
     dp[i][j] = min(dp[i][j],dp[i][j-1] + min(a[str[j]-'a'], b[str[j]-'a']));
   }
 }
 printf("%d\n",dp[0][m-1]);
   return 0;
}