Browse Tag

动态规划

POJ 1080 Human Gene Functions (DP)

  • @ 千千
  • /
  • 发表于 2017 年 02 月 07 日
  • /
  • 线性DP
  • /
    • 2,108 次围观

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

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

POJ 1837 Balance (01背包)

有一个天平，左臂右臂各长15，然后给出c，g。

c代表有几个挂钩，挂钩给出负数代表在左臂的距离，正数则在右臂；

g代表有几个砝码，要你求出使得这个天平保持平衡有几种方法，要求所有砝码全部使用完。

POJ 1276 Cash Machine (多重背包)

一个取款机有N种钞票，每种钞票有nk张，面额为Dk，给定一个取款金额cash，可行的、不超过该金额的吐钞方案最大是多少钱？

POJ 3267 The Cow Lexicon (DP)

  • @ 千千
  • /
  • 发表于 2017 年 02 月 07 日
  • /
  • 线性DP
  • /
    • 2,180 次围观

给出一个原始序列，以及w个单词，问该序列至少需要去掉多少个字母之后，才能变成完全由已知单词构成的序列。