首页 > 代码库 > POJ 3280 Cheapest Palindrome (区间dp)
POJ 3280 Cheapest Palindrome (区间dp)
题目大意:
给你m个字符,其中有n种字符,每种字符都有两个值,分别是增加一个这样的字符的代价,删除一个这样的字符的代价,让你求将原先给出的那串字符变成回文串的最小代价。
思路分析:
状态方程:dp[i][j] 表示 区间 i-j是回文串的最小代价。
状态转移:
有三种情况。
1、 i+1 ~ j 已经是回文串了,那么对于 i 这个字符,要么删除掉,要么在这个回文串后面加一个 str[i]...
2、i~ j-1 已经是回文串了,那么对于j 这个字符,要么删除掉,要么在这个回文串前面加一个str j
3、i ~ j 已经是一个回文串了,那么就要比较 dp [i+1] [j-1] 和 dp[i][j] 的大小。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define maxn 2005 using namespace std; char str[maxn]; int dp[maxn][maxn]; int add[maxn]; int cost[maxn]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { scanf("%s",str+1); char ch[5]; for(int i=1;i<=n;i++) { scanf("%s",ch); scanf("%d%d",&add[ch[0]],&cost[ch[0]]); } memset(dp,0,sizeof dp); for(int i=m-1;i>=1;i--) { for(int j=i+1;j<=m;j++) { dp[i][j]=min(dp[i+1][j]+add[str[i]],dp[i+1][j]+cost[str[i]]); dp[i][j]=min(dp[i][j],min(dp[i][j-1]+add[str[j]],dp[i][j-1]+cost[str[j]])); if(str[i]==str[j])dp[i][j]=min(dp[i][j],dp[i+1][j-1]); } } printf("%d\n",dp[1][m]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。