本题为典型的动态规划,关键找出序列比对的3个不同情况,即子问题
设d[i][j]为取s1第i个字符,s2第j个字符时的最大分值
则决定p为最优的情况有三种 p数组为分数矩阵
1、 s1取第i个字母,s2取“ - ”: d[i-1][j]+p[ s1[i-1] ]['-'];
2、 s1取“ - ”,s2取第j个字母:d[i][j-1]+p['-'][ s2[j-1] ];
3、 s1取第i个字母,s2取第j个字母:d[i-1][j-1]+p[ s1[i-1] ][ s2[j-1] ];
即dp[i][j]为上述三种情况的最大值
易犯错误
1、p数组的初始化,不细心的话容易犯错(因为这个低级错误WA两次- -)
2、d[0][j],d[i][0],d[0][0]边界值的赋值
Source Code
Problem: 1080
|
|
User:
yangliuACMer
|
Memory: 568K |
|
Time: 0MS |
Language: C++ |
|
Result: Accepted
|
分享到:
相关推荐
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ1080-Human Gene Functions
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
北大POJ初级-动态规划 解题报告+AC代码
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
3.徐持衡《浅谈几类背包题》 8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack 【专辑】插头DP 【专辑】单调队列+斜率优化的DP ...最长公共子序列和字符串相似度 最大矩阵连乘次数(最小连乘变形)
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(马尔科夫矩阵,求...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
poj online judge 1050 最大子矩阵动态规划解决
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
动态规划DP题解 POJ HDU 动态规划解题报告
poj分类poj分类poj分类poj分类