[POJ - 3280] Cheapest Palindrome

发表于 | 更新于 | 分类于 ， ，
本文字数： 11k

链接

\(\text{POJ - 3280}\)

题意

  给你一个长度为\(\text{M}\)的由小写字母组成的字符串\(s\)，你希望通过插入字符或者删除字符的操作来得到一个回文串，你希望操作次数最少；同时对于\(26\)种字符中的字符\(i\)，有对应的删除该字符需要的花费\(cost_1\)和插入该字符需要的\(cost_2\)，所以你希望通过插入和删除操作并且花费尽量少的钱来获取一个回文串。

  数据范围：\(1\leq \text{M} \leq 500\)，\(0\le cost\le 10000\).

分析

  这是一道区间\(dp\)的题目；

  通过对字符串的插入、删除、修改来获取一 个回文串，然后求最少次数，这是一类比较典型且常见的区间\(dp\)题目；

  区间\(dp\)即是小区间状态到大区间状态的合并或者说转移，一般我们都会枚举小区间，然后枚举起始点；

  如对于一个串\(aba\)，假设区间长度为\(2\)的阶段的所有状态我们已经求出来了，那么此时区间长度为\(3\)，对于这个串来说，我们肯定需要看它的两个短点\(i\)与\(j\)，\(s[i]==s[j]\)，我们就得出了\(dp[i][j]=dp[i+1][j-1]\)，这是很显然的；那么对于一个串\(aab\)，如果我们也已经求出来了它的区间长度为\(2\)的状态，那么此时对于区间长度为\(3\)的状态，我们观察它的\(s[i]!=s[j]\)，如果同时把这两个字符都给删掉或者给两个字符均插入一个匹配的字符，那么这显然是糟糕的选择，所以我们不能这样做；最终我们可以得出\(dp[i][j]=min(dp[i+1][j]+cost[i],dp[i][j-1]+cost[j])\)

  对于价格来说，其实都是一样的，不论插入和删除本质上都是一样的，所以我们仅需要考虑价格即可，对于每个字符，使用价格低的操作，初始状态\(dp[i][i]=0\)。

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
	//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
	//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
	inline int read() {
		char c = getchar(); int x = 0, f = 1;
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
}

using namespace fastIO;
using namespace std;

int t, n, m, a[300], dp[2005][2004];
string s;
int main() {
	while (cin >> n >> m) {
		cin >> s;
		int x, y;
		char t;
		for (int i = 1; i <= n; i++) {
			cin >> t >> x >> y;
			a[t] = min(x, y);
		}
		for (int len = 2; len <= m; len++)
			for (int i = 1; i + len - 1 <= m; i++) {
				int j = i + len - 1;
				dp[i][j] = INF;
				if (s[i - 1] == s[j - 1])
					dp[i][j] = dp[i + 1][j - 1];
				else {
					dp[i][j] = min(dp[i][j], dp[i + 1][j] + a[s[i - 1]]);
					dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[s[j - 1]]);
				}
			}
		cout << dp[1][m] << endl;
	}
}