SSL 2671_呀!回文串_dp

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


题目描述

小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]);
}

 

]]>


「墨泼三千烟火,许你一世迷离」