首页 > 代码库 > poj3280（区间dp）
poj3280（区间dp）
题目连接：http://poj.org/problem?id=3280
题意：给定一个长度为m(m<=2000)的小写字母字符串，在给定组成该字符串的n(n<=26)个字符的添加和删除费用，求使原字符串变为回文串的最小费用。
分析：首先明确，删除一个字母和增加一个字母是等价的，如果删除一个字符一个字符使得原字符串变成回文，那么必定可以增加一个字符使原字符串变成回文，因此对于删除和增加操作去费用最少的即可。
dp[i][j]表示区间i~j形成回文串最少费用，则：
dp[i][j] = min(dp[i+1][j]+cost[str[i]-‘a‘], dp[i][j-1]+cost[str[j]-‘a‘]);
if(str[i] == str[j])dp[i][j] = min(dp[i][j],dp[i+1][j-1]);
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int cost[30],dp[2110][2110];char s[10],str[2100];int dfs(int l,int r){ if(dp[l][r]!=-1)return dp[l][r]; if(l>=r)return 0; int temp=inf; if(str[l]==str[r]) temp=min(temp,dfs(l+1,r-1)); temp=min(temp,dfs(l+1,r)+cost[str[l]-‘a‘]); temp=min(temp,dfs(l,r-1)+cost[str[r]-‘a‘]); return dp[l][r]=temp;}int main(){ int n,m; while(scanf("%d%d",&n,&m)>0) { scanf("%s",str+1); for(int i=1;i<=n;i++) { int add,det; scanf("%s%d%d",s,&add,&det); cost[s[0]-‘a‘]=min(add,det); } FILL(dp,-1); printf("%d\n",dfs(1,m)); }}
poj3280（区间dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。