POJ 3280 Cheapest Palindrome 题解 《挑战程序设计竞赛(第2版)》

2.3 记录结果再利用的“动态规划” 基础的动态规划算法

POJ 3280 Cheapest Palindrome

字串S长M，由N个小写字母构成。欲通过增删字母将其变为回文串，增删特定字母花费不同，求最小花费。

定义dp[i][j]表示将原字串s的子字串s[i…j]变换成回文的最小花费，满足如下递推关系式：

dp[i][j] = min(	dp[i + 1][j] + cost[s[i] - 'a'],	// 比i, j少了一个首字母
							dp[i][j - 1] + cost[s[j] - 'a']);	// 比i, j少了一个尾字母
			if (s[i] == s[j])
			{
				// 首尾相同，等于少了首尾
				dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
			}

注意此处的可以增加也可以删除是个局，取其花费最小值即可。因为如果在首尾增删字母x都可以使一个字串s[i…j]变成回文的话，当然选取花费小的。

另一个注意点是两重循环的方向，起点i应当趋0，终点j应当趋M。

#include <iostream>
#include <string>
using namespace std;

int cost[32];
int dp[2048][2048];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N, M;
	cin >> N >> M;
	string s;
	cin >> s;
	for (int i = 0; i < N; ++i)
	{
		char c;
		int add_cost, delete_cost;
		cin >> c >> add_cost >> delete_cost;
		cost[c - 'a'] = min(add_cost, delete_cost);
	}
	for (int i = M - 1; i >= 0; --i)
	{
		for (int j = i + 1; j < M; ++j)
		{
			dp[i][j] = min(	dp[i + 1][j] + cost[s[i] - 'a'],	// 比i, j少了一个首字母
							dp[i][j - 1] + cost[s[j] - 'a']);	// 比i, j少了一个尾字母
			if (s[i] == s[j])
			{
				// 首尾相同，等于少了首尾
				dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
			}
		}
	}

	cout << dp[0][M - 1] << endl;

#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3280 Cheapest Palindrome 题解 《挑战程序设计竞赛(第2版)》