
POJ 2229 Sumsets 题解 《挑战程序设计竞赛(第2版)》
2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 2229 Sumsets 将一个数N分解为2的幂之和共有几种分法? 定义dp[i]为i的分解方案数。dp[0] = 2 ^ 0 = 1,递推到 N 。若i为偶数,则dp[i]...
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 给定海岛个数、雷达半径以及各海岛坐标,求能覆盖所有海岛的最小雷达数。 贪心策略依然是从左往右,尽量让每颗雷达覆盖最大岛屿数。 对整个题目数据的处理有个思...
2.2 一往直前!贪心法 区间 POJ 2376 Cleaning Shifts 给定N个小区间以及区间起点终点,求能用它们覆盖区间[1,T]的最小组合。 贪心策略是从左往右,尽量选择长度最大的区间。 首先对所有奶牛排序,按照开始时间排序。...