
POJ 2385 Apple Catching 题解 《挑战程序设计竞赛(第2版)》
2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 2385 Apple Catching 2棵苹果树在T分钟内随机由某一棵苹果树掉下一个苹果,奶牛站在树#1下等着吃苹果,它最多愿意移动W次,问它最多能吃到几个苹果。 定义dp...
2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 2385 Apple Catching 2棵苹果树在T分钟内随机由某一棵苹果树掉下一个苹果,奶牛站在树#1下等着吃苹果,它最多愿意移动W次,问它最多能吃到几个苹果。 定义dp...
2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 2229 Sumsets 将一个数N分解为2的幂之和共有几种分法? 定义dp[i]为i的分解方案数。dp[0] = 2 ^ 0 = 1,递推到 N 。若i为偶数,则dp[i]...
2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 3176 Cow Bowling 奶牛保龄球:金字塔形的保龄球中从顶往下撞击,每次只能撞击左下或右下两个,求所有撞到得分的最高值。 最基础的dp吧,用dp[i][j]表示第i...
2.2 一往直前!贪心法 其他 POJ 3262 Protecting the Flowers 保护祖国的花朵:约翰的奶牛每分钟吃掉D_i朵花,把它赶走需要T_i分钟(来回加倍)。问最小损失花朵数量。 贪心策略是尽量赶走吃得多并且走得慢的牛...
2.2 一往直前!贪心法 其他 POJ 1862 Stripies 变形虫:从N个数任取两个数按2*sqrt(a*b)合成新数放回,求最后那个数的最小值。 贪心策略是使尽量使大的数多参与开放运算。每次取出最大和次大的变形虫杂交,直至剩下一条...
2.2 一往直前!贪心法 其他 POJ 3040 Allowance 农夫约翰要给奶牛Bessie发工资了(你们结婚吧,生个牛头人( ̄_ ̄|||) ),每周至少 C 元。约翰手头上有面值V_i的硬币B_i个,这些硬币的最小公约数为硬币的最小...
2.2 一往直前!贪心法 其他 POJ 1017 Packets 有 1 * 1 到 6 * 6 的产品,最少用几个 6 * 6 的箱子装它们。 贪心策略是先装大的,再装小的,看我专门画的图就全明白了。生活常识,桶里先放碎石,再放沙,最后还...
2.2 一往直前!贪心法 其他 POJ 2393 Yogurt factory 奶牛们建了一家酸奶厂,在N周内每周需要出货Y_i单位酸奶,第i周成本为C_i,储存费为每周Y。求总体最低成本。 贪心策略是维持每周的最低单位成本,每周可能用上周...
2.2 一往直前!贪心法 区间 POJ 3190 Stall Reservations 还是该死的奶牛,这一回它们很淘气,每一只奶牛要求在时间区间[A,B]内独享一个牛栏。问最少需要多少个牛栏。 贪心策略是优先满足A最小的奶牛,维持一个牛栏...
2.2 一往直前!贪心法 区间 POJ 1328 Radar Installation 给定海岛个数、雷达半径以及各海岛坐标,求能覆盖所有海岛的最小雷达数。 贪心策略依然是从左往右,尽量让每颗雷达覆盖最大岛屿数。 对整个题目数据的处理有个思...