POJ3280 Cheapest Palindrome 区间DP

给你一个字符串，把它变成回文串，可以添加字母也可以删除其中的字母，对于每一个字母添加和删除需要不同的花费，问使得这个字符串变成回文串最少需要花多少

区间DP，从后向前推，如果区间[i,j]  s[i] == s[j]，那么dp[i][j] = dp[i+1][j-1], 如果不想等 那么要么是加上一个 或者删除一个，在这里举个例子把，当推到abcb的时候，操作无非两种 删除a或者加上一个a，这两个操作其实是一样的只不过花费不一样，所以可以直接取添加删除中花费较小的那个即可，这样就不用太多的状态转移方程了，一开始添加删除分开写的 有点繁琐，写到一半觉得是一样的

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-8

#define inf 0xfffffff
//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

//#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin)  
//#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) 

int dp[3000 + 5][3000 + 5];
int cost[1000 + 5];

string s;

typedef struct Node {
	string str;
	int get,lose;
};

Node node[10000 + 5];

void clear() {
	memset(dp,0,sizeof(dp));
	memset(node,0,sizeof(node));
	memset(cost,0,sizeof(cost));
}

int main() {
	int n,m;
	while(cin>>n>>m) {
		clear();
		cin>>s;
		for(int i=0;i<n;i++) {
			cin>>node[i].str>>node[i].get>>node[i].lose;
			cost[node[i].str[0] - ‘a‘] = min(node[i].get,node[i].lose);
		}
		for(int i=m-1;i>=0;i--) {
			for(int j=i+1;j<m;j++) {
				if(s[i] == s[j])
					dp[i][j] = dp[i+1][j-1];//两头的相等就不需要处理了
				else
					dp[i][j] = min(dp[i+1][j] + cost[s[i]-‘a‘],dp[i][j-1] + cost[s[j]-‘a‘]);//两头不等，是加一个相同的或者取出一个比较大小
			}
		}
		printf("%d\n",dp[0][m-1]);
	}
	return EXIT_SUCCESS;
}

POJ3280 Cheapest Palindrome 区间DP,布布扣,bubuko.com

POJ3280 Cheapest Palindrome 区间DP

原文：http://blog.csdn.net/yitiaodacaidog/article/details/19937313