Browse Tag

POJ

POJ 3026 Borg Maze (最小生成树)

从 S 出发,去到达每一个 A ,求最小的总路径长度,空格是空地,# 是墙,并且在走的过程中我们可以在 S 或 A 点分裂,也就是从该点可以延伸出多条路径到其他点,但是每一次只能让其中的一个继续行走。

POJ 1080 Human Gene Functions (DP)

给定两个基因字符串,用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)

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

POJ 1836 Alignment (LIS)

求删除最少的数,使得序列中任取一个 a[i],使得有 a[0]~a[i] 严格递增,a[i]~a[n-1]严格递减。