洛谷 P4059 [Code+#1]找爸爸
code 洛谷
2023-09-11 14:20:14 时间
洛谷 P4059 [Code+#1]找爸爸
题目描述
小A最近一直在找自己的爸爸,用什么办法呢,就是DNA比对。
小A有一套自己的DNA序列比较方法,其最终目标是最大化两个DNA序列的相似程度,具体步骤如下:
- 给出两个DNA序列,第一个长度为nn,第二个长度为mm。
- 在两个序列的任意位置插入任意多的空格,使得两个字符串长度相同
- 逐位进行匹配,如果两个序列相同位置上的字符都不是空格,假设第一个是xx,第二个是yy,那么他们的相似程度由d(x,y)d(x,y)定义。对于两个序列中任意一段极长的长度为kk的连续空格,我们定义这段空格的相似程度为g(k)=-A-B(k-1)g(k)=−A−B(k−1)。
那么最终两个序列的相似程度就是所有的d(x,y)d(x,y)加上所有的极长空格段的相似程度之和。
现在小A通过某种奥妙重重的方式得到了小B的DNA序列中的一段,他想请你帮他算一下小A的DNA序列和小B的DNA序列的最大相似程度。
输入格式
输入第11行一个字符串,表示小A的DNA序列。
输入第22行一个字符串,表示小B的DNA序列。
接下来44行,每行44个整数,用空格隔开,表示dd数组,具体顺序如下所示。
d(A,A) d(A,T) d(A,G) d(A,C)
d(T,A) d(T,T) d(T,G) d(T,C)
d(G,A) d(G,T) d(G,G) d(G,C)
d(C,A) d(C,T) d(C,G) d(C,C)
最后一行两个用空格隔开的正整数A,BA,B,意义如题中所述。
输出格式
输出共一行,表示两个序列的最大相似程度。
题解:
2020.11.26模拟赛T2 85分场
挂分了。
看出来是DP,但是状态啊转移啊什么的好像都不是很好想。
肯定决策就是空格、这9种情况选一个。但是这个空格的长度怎么维护啊。
后来苦思冥想憋出来一个状态还写挂了。
反正就是积累一些DP的宝贵经验吧。
相关文章
- 什么是代码?code?
- How to setup Visual Studio Code to detect and set the correct encoding on file open
- 'workspace' in VS Code
- XCODE插件 之 Code Pilot 无鼠标化
- PyCharm使用技巧:Inspect Code(代码静态审查)
- CDMA(Code Division Multiple Access码分多址)
- Visual Studio Code
- Android5.0(Lollipop) BLE蓝牙4.0+浅析code(二)
- Visual Studio Code
- 浅析如何升级vue-cli以及使用npm卸载包时遇到问题:npm ERR! code EEXIST(npm ERR! File exists: D:Programnodejsnode_globalvue-list.cmd - npm ERR! Move it away, and try again.)
- OPatch failed with error code 73(OracleHomeInventory gets null oracleHomeInfo)
- 为什么企业里用 VS Code 的这么多?
- USACO holstein AC code
- [LintCode] Gray Code 格雷码
- How to fix “HTTP Status Code 505 – HTTP Version Not Supported” error?--转
- Job for httpd.service failed because the control process exited with error code.