SSL 2671_呀!回文串_dp

发布于 2017-08-08  878 次阅读

题目描述

小B的名字是由前n个小写字母组成的一个长度为m字符串。一天，小B看上了一个金发碧眼的漂亮妹子，但妹子在知道了小B的名字后，就无情地抛弃了小B，而原因竟然是小B的名字不够优美！在小B的追问下，妹子告诉小B，只有回文串是优美的。于是小B决定把自己的名字变得优美，但每加入或删除一个字母都要付出一定的代价。为了小B的人生大事，请你告诉小B他最少需要付出多少代价。

 

思路

用f[i][j]表示[i..j] 这个区间已经是回文串所用的最小花费

a表示加上这个字符的花费，b表示删掉这个字符的花费，那么显然就有几种状态的转移

即可以同时删除，将左右的其中一个替换，删除或添加一个字符

#include 
#include 
#include 
#include 
using namespace std;
#define fill(x, y) memset(x, y, sizeof(x))
#define min(x, y) (x) < (y) ? (x) : (y)
#define INF 0x7f7f7f7f
char str[10005];
int a[1050], b[1005], f[5001][5001];
int main()
{

    int n, m;
    scanf("%d%d", &m, &n);
    cin >> str;
    for (int i = 1; i <= m; i++)
    {
        char ch;
        cin >> ch;
        cin >> a[ch] >> b[ch];
    }
    for (int k = 2; k <= n; k++)
        for (int i = 1; i <= n - k + 1; i++)
        {
            int j = i + k - 1;
            f[i][j] = INF;
            if (str[i - 1] == str[j - 1])
                f[i][j] = min(f[i][j], f[i + 1][j - 1]);
            else
            {
                f[i][j] = min(f[i][j], f[i + 1][j - 1] + b[str[i - 1]] + b[str[j - 1]]);
                f[i][j] = min(f[i][j], f[i + 1][j - 1] + b[str[j - 1]] + b[str[i - 1]]);
            }
            f[i][j] = min(f[i][j], f[i + 1][j - 1] + b[str[i - 1]] + a[str[j - 1]]);
            f[i][j] = min(f[i][j], f[i + 1][j] + b[str[i - 1]]);
            f[i][j] = min(f[i][j], f[i + 1][j] + a[str[i - 1]]);
            f[i][j] = min(f[i][j], f[i][j - 1] + b[str[j - 1]]);
            f[i][j] = min(f[i][j], f[i][j - 1] + a[str[j - 1]]);
    }
    printf("%d\n", f[1][n]);
}

 

]]>