POJ 3280 Cheapest Palindrome(DP 回文变形)
2024-08-22 04:02:09
题目链接:http://poj.org/problem?id=3280
题目大意:给定一个字符串,可以删除增加,每个操作都有代价,求出将字符串转换成回文串的最小代价
Sample Input
3 4
abcb
a 1000 1100
b 350 700
c 200 800
Sample Output
900
分析:这是一道最长回文串的变形,就是LCS
一串字符要变成回文,对于一个字符来说,删掉它,或者增加对称的一个该字符,都能达到回文的效果,所以是等价的。所以取代价的的时候选择最小的就可以。
至于动态规划方程:令dp[i][j]表示从第 i 个字符到第j个字符变成回文的最小代价,初始为0。接着LCS
dp[i][j] = min(dp[i+1][j]+cost[s[i]-'a'] , dp[i][j-1]+cost[s[j]-'a']) ;
if(s[i]==s[j]) dp[i][j] = min(dp[i+1][j-1],dp[i][j]);
代码如下:
# include<stdio.h>
# include<string.h>
# define maxn
char s[maxn];
int dp[maxn][maxn],cost[maxn]; int min(int a,int b){
return a<b ? a :b;
} int main(){
int n,m,a,b,i,j;
char temp;
while(scanf("%d%d",&n,&m)!=EOF){
memset(dp,,sizeof(dp));
getchar();
scanf("%s",s+);
getchar();
for(i=;i<=n;i++){
scanf("%c %d%d",&temp,&a,&b);
getchar();
cost[temp-'a'] = min(a,b);
}
for(j=;j<=m;j++){
for(i=j+;i>=;i--){
dp[i][j] = min(dp[i+][j]+cost[s[i]-'a'] , dp[i][j-]+cost[s[j]-'a']) ;
if(s[i]==s[j])
dp[i][j] = min(dp[i+][j-],dp[i][j]);
}
}
printf("%d\n",dp[][m]);
}
return ;
}
最新文章
- autofs自动挂载
- Shiro-HelloWord
- USACO翻译:USACO 2014 MARCH Silver三题
- maven常用插件pom配置
- Go+sublime text3的环境搭建
- Java for LeetCode 206 Reverse Linked List
- (IOS)BaiduFM 程序分析
- 深入浅出设计模式——工厂方法模式(Factory Method)
- HDU-3853 LOOPS(概率DP求期望)
- windows phone版的一个儿教app
- C#.NET学习笔记7--11---算术运算符,变量赋值,变量的交换,布尔表达式1,布尔表达式2
- Swift入门教程:基本运算符
- 树上差分 (瞎bb) [树上差分][LCA]
- 【Linux】管理在线用户
- C++头文件用<;>;还是“” 以及 要加.h还是不加 的问题
- js的一些
- [转]TFS常用的命令行详解
- 【代码笔记】iOS-自定义alertView
- springmvc的声明式事务管理类型讲解
- elk6.22
热门文章
- poj 2451 Uyuw&#39;s Concert(半平面交)
- [ZETCODE]wxWidgets教程七:对话框
- 关于yuv 的pack(紧缩格式)和planner(平面格式)格式 [转]
- 激活Navicat?如何注册Navicat?
- Nice validator领先的表单验证解决方案 转
- 是否以某字符串结尾 是否以某字符串开始 是否是整数 裁减字符串空格 是否是浮点数 是否所有字符为数字类型 是否为空 是否是EMAIL	 是否是电话号码 身份证号码验证-支持新的带x身份证 日期验证
- 通讯录改造——MVC设计模式
- SQL SERVER 中如何将NULL转换为0
- 史上比较用心的纯代码实现 AutoLayout
- CCEditBox用法