poj3280:http://poj.org/problem?id=3280
简单的多子问题多选择dp问题:
dp[i][j]表示字符下标为i到j的子字符串构成回文的最小消费,构成解的子问题有以下两种情况:
1、str[i]!=str[j],则最小费用为dp[i][j]=min{dp[i+1][j]+cost(str[i]),dp[i][j-1]+cost[str[j]]},其中cost(char),是取得增加和删除该字符的费用较小值;
2、str[i]==str[j],则最小费用为dp[i][j]=min{dp[i][j],dp[i+1][j-1]},保证此时dp[i][j]已经求出。
简单的多子问题多选择dp问题:
dp[i][j]表示字符下标为i到j的子字符串构成回文的最小消费,构成解的子问题有以下两种情况:
1、str[i]!=str[j],则最小费用为dp[i][j]=min{dp[i+1][j]+cost(str[i]),dp[i][j-1]+cost[str[j]]},其中cost(char),是取得增加和删除该字符的费用较小值;
2、str[i]==str[j],则最小费用为dp[i][j]=min{dp[i][j],dp[i+1][j-1]},保证此时dp[i][j]已经求出。
#include <iostream> #include <fstream> #define MAX_DP 2011 using namespace std; char str[MAX_DP]; unsigned int dp[MAX_DP][MAX_DP]; int cost[26]; unsigned int min(unsigned int a,unsigned int b) { if(a>=b) return b; else return a; } unsigned int dodp(unsigned int start,unsigned int end) { if(start>=end) return 0; if(dp[start][end]) return dp[start][end]; dp[start][end]=min(dodp(start+1,end)+cost[str[start]-'a'],dodp(start,end-1)+cost[str[end]-'a']); if(str[start]==str[end]) dp[start][end]=min(dp[start][end],dodp(start+1,end-1)); return dp[start][end]; } int main() { unsigned int m,n; memset(cost,0,sizeof(cost)); memset(dp,0,sizeof(dp)); cin>>n>>m; cin>>str; for(int i=0;i<n;i++) { char temp; unsigned int a,b; cin>>temp; cin>>a>>b; cost[temp-'a']=min(a,b); } cout<<dodp(0,m-1)<<endl; return 0; }
发表评论
-
2011清华考研机试题2
2011-08-09 14:56 907http://ac.jobdu.com/problem.php ... -
2011清华考研机试题1
2011-08-09 14:40 642题目描述 http://ac.jobdu.com/proble ... -
考研清华2011复试机考第三题
2011-08-09 13:51 1490题目描述 在某条线路上有N个火车站,有三种距离的路程,L1, ... -
poj3259 spfa解法
2011-08-08 19:59 1356同上题,不过改的spfa算法,注意每个节点进入队列的次数至多为 ... -
poj3259 bellman水题
2011-08-08 17:04 969poj3259http://poj.org/problem?i ... -
acm题目常用的预处理
2011-08-08 15:26 1163#include<iostream> #in ... -
poj1860
2011-08-08 14:06 704poj1860http://poj.org/problem?i ... -
water~9
2011-08-06 18:01 417poj2109http://poj.org/problem?i ... -
water~8
2011-08-06 17:22 573poj2027http://poj.org/problem?i ... -
water~7
2011-08-06 17:15 567poj1328http://poj.org/problem?i ... -
water~6
2011-08-06 14:27 706poj1088http://poj.org/problem?i ... -
water~5
2011-08-06 14:24 581poj1003http://poj.org/problem?i ... -
water~4
2011-08-06 14:09 636poj1004http://poj.org/problem?i ... -
water~3
2011-08-06 13:59 522poj2159http://poj.org/problem?i ... -
water~2
2011-08-06 12:10 533poj3299http://poj.org/problem?i ... -
water~1
2011-08-06 10:35 639poj1503http://poj.org/problem?i ... -
POJ3253
2011-08-04 13:36 779poj3253:http://poj.org/problem? ...
相关推荐
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
如果有了这个的话,学习起来更系统,更清爽!
北大POJ3411-Paid Roads【class】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
2遍dp poj_3613解题报告 poj_3613解题报告
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告