放牧代码和思想
专注自然语言处理、机器学习算法

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版)》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    for (int i = M – 1; i >= 0; –i) 为什么要从后面开始,我试了i从0开始会WA,为什么起点i应当趋0,终点j应当趋M?
    if(s [i] ==s [j] ){//这里考虑两边删除相同字母,为什么不考虑两边加上相同字母

    林瑞玉19942年前 (2015-06-03)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机