POJ3280 Cheapest Palindrome

发表于 | 分类于 |
字数统计: 398 | 阅读时长 ≈ 1

题面：http://poj.org/problem?id=3280

题意

给定一个字符串，允许你删除或者新增一些字母构造出一个回文串。构造和新增每个字母的代价都不同，求最小代价。

解法

区间dp
首先增加和删除的代价不同是骗人的。
对于字符串abb，你可以选择新增字符a, 也可以选择删掉字符a
所以只要保存删除的增加的最小值即可。
然后是一个区间dp
令$dp[i][j]$表示第i个位置和第j个位置组成的字符串要形成回文串的最小代价。
思考一下可以得到以下转移方程：

1
2
3
4
if s[i] = s[j] 
	dp[i][j] = dp[i + 1][j - 1] 
else
	dp[i][j] = min(dp[i + 1][j] + val[s[i]], dp[i][j - 1] + val[s[j]])

最后$dp[0][len - 1]$就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iostream>
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 2e3 + 10;
int val[50];
int dp[maxn][maxn];
char s[maxn];
//dp[i][j]表示从i到j要形成回文串的最小代价
int main()
{
    int n, m;
    scanf("%d%d%s", &n, &m, s);
    while(n--)
    {
        getchar();
        char c;
        int x, y;
        scanf("%c%d%d", &c, &x, &y);
        val[c - 'a'] = min(x, y);
    }
    for(int j = 1; j < m; j++)
        for(int i = 0; i < m && i + j < m; i++)
        {
            if(s[i] == s[i + j])
                dp[i][i + j] = dp[i + 1][i + j - 1];
            else
                dp[i][i + j] = min(dp[i][i + j - 1] + val[s[i + j] - 'a'], dp[i + 1][i + j] + val[s[i] - 'a']);
        }
    printf("%d\n", dp[0][m - 1]);
    return 0;
}