2014-02-09阅读(5240)评论(4)

POJ 3181 Dollar Dayz 农夫约翰有N元钱，市场上有价值1……K的商品无限个，求所有的花钱方案？ 这是一个完全背包问题和大数的混合题目。 《2.3 记录结果再利用的“动态规划” 优化递推关系式》练习题的第三题。 定义&nbs...

2014-02-09阅读(5982)评论(1)

POJ 3046 Ant Counting 蚂蚁牙黑，蚂蚁牙红：有A只蚂蚁，来自T个家族。同一个家族的蚂蚁长得一样，但是不同家族的蚂蚁牙齿颜色不同。任取n只蚂蚁(S<=n<=B)，求能组成几种集合？ 这是《2.3 记录结果再利用...

2014-02-08阅读(8770)评论(3)

POJ 1742 Coins 传说中的男人八题，是男人就A这八题。有n种面额的硬币，面额个数分别为A_i、C_i，求最多能搭配出几种不超过m的金额？ 这是一个多重部分和问题(多重背包问题)，放在了《2.3 记录结果再利用的“动态规划” 优化...

2014-02-07阅读(5704)评论(1)

2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 3280 Cheapest Palindrome 字串S长M，由N个小写字母构成。欲通过增删字母将其变为回文串，增删特定字母花费不同，求最小花费。 定义dp[i][j]表示将...

2014-02-07阅读(5652)评论(0)

2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 3616 Milking Time 奶牛Bessie在0~N时间段产奶。农夫约翰有M个时间段可以挤奶，时间段f,t内Bessie能挤到的牛奶量e。奶牛产奶后需要休息R小时才能...

2014-02-07阅读(4516)评论(0)

2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 2385 Apple Catching 2棵苹果树在T分钟内随机由某一棵苹果树掉下一个苹果，奶牛站在树#1下等着吃苹果，它最多愿意移动W次，问它最多能吃到几个苹果。 定义dp...

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

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

2014-02-06阅读(4262)评论(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阅读(4344)评论(1)

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