2014年02月的文章

2014-02-06阅读(5115)评论(2)

2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 2229 Sumsets 将一个数N分解为2的幂之和共有几种分法？ 定义dp[i]为i的分解方案数。dp[0] = 2 ^ 0 = 1，递推到 N 。若i为偶数，则dp[i]...

2014-02-06阅读(4270)评论(0)

2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 3176 Cow Bowling 奶牛保龄球：金字塔形的保龄球中从顶往下撞击，每次只能撞击左下或右下两个，求所有撞到得分的最高值。 最基础的dp吧，用dp[i][j]表示第i...

2014-02-06阅读(3835)评论(0)

2.2 一往直前！贪心法 其他 POJ 3262 Protecting the Flowers 保护祖国的花朵：约翰的奶牛每分钟吃掉D_i朵花，把它赶走需要T_i分钟（来回加倍）。问最小损失花朵数量。 贪心策略是尽量赶走吃得多并且走得慢的牛...

2014-02-06阅读(4350)评论(1)

2.2 一往直前！贪心法 其他 POJ 1862 Stripies 变形虫：从N个数任取两个数按2*sqrt(a*b)合成新数放回，求最后那个数的最小值。 贪心策略是使尽量使大的数多参与开放运算。每次取出最大和次大的变形虫杂交，直至剩下一条...

2014-02-06阅读(6020)评论(6)

2.2 一往直前！贪心法 其他 POJ 3040 Allowance 农夫约翰要给奶牛Bessie发工资了（你们结婚吧，生个牛头人(￣_￣|||) ），每周至少 C 元。约翰手头上有面值V_i的硬币B_i个，这些硬币的最小公约数为硬币的最小...

2014-02-06阅读(4135)评论(0)

2.2 一往直前！贪心法 其他 POJ 1017 Packets 有 1 * 1 到 6 * 6 的产品，最少用几个 6 * 6 的箱子装它们。 贪心策略是先装大的，再装小的，看我专门画的图就全明白了。生活常识，桶里先放碎石，再放沙，最后还...

2014-02-05阅读(4277)评论(0)

2.2 一往直前！贪心法 其他 POJ 2393 Yogurt factory 奶牛们建了一家酸奶厂，在N周内每周需要出货Y_i单位酸奶，第i周成本为C_i，储存费为每周Y。求总体最低成本。 贪心策略是维持每周的最低单位成本，每周可能用上周...

2014-02-05阅读(5547)评论(2)

2.2 一往直前！贪心法 区间 POJ 3190 Stall Reservations 还是该死的奶牛，这一回它们很淘气，每一只奶牛要求在时间区间[A,B]内独享一个牛栏。问最少需要多少个牛栏。 贪心策略是优先满足A最小的奶牛，维持一个牛栏...

2014-02-04阅读(5139)评论(6)

2.2 一往直前！贪心法 区间 POJ 1328 Radar Installation 给定海岛个数、雷达半径以及各海岛坐标，求能覆盖所有海岛的最小雷达数。 贪心策略依然是从左往右，尽量让每颗雷达覆盖最大岛屿数。 对整个题目数据的处理有个思...

2014-02-03阅读(5769)评论(0)

2.2 一往直前！贪心法 区间 POJ 2376 Cleaning Shifts 给定N个小区间以及区间起点终点，求能用它们覆盖区间[1,T]的最小组合。 贪心策略是从左往右，尽量选择长度最大的区间。 首先对所有奶牛排序，按照开始时间排序。...