Browse Category

线性DP

URAL 2018. The Debut Album (dp)

一个长度为 n 的数列,其中 1 连续的个数不能超过 a , 2 连续的个数不能超过 b ,问总共有多少个这样的数列。

POJ 1925 Spiderman (DP)

蜘蛛侠在第一个建筑物上,他要去最后一个建筑救女朋友,每一次蜘蛛侠可以摇摆到关于建筑对称的位置,且丝线长度不能大于建筑物的高度,求到最后一个建筑的最小摇摆次数。

POJ 1080 Human Gene Functions (DP)

给定两个基因字符串,用A,C,G,T表示其组成成分。

若两个基因的长度不一样,可以通过在两个串中分别添加空格使其长度一致,当其长度一样后,分别计算对应位置上的两个字母的分数,并将所有的分数相加便得到两个串的相似度分数,求最高分数。