2014-02-14阅读(5133)评论(0)

POJ 2392 Space Elevator 通天塔：奶牛们想用c_i个高h_i的积木造通天塔，每种积木不能高过a_i，求塔的最大高度。 多重背包 O(VN) 单调队列  这题要思考的方向是往多重背包这边想，...

2014-02-11阅读(8052)评论(5)

POJ 3666 Making the Grade 农夫约翰想修一条尽量平缓的路，路的每一段海拔是A_i，修理后是B_i，花费|A_i – B_i|，求最小花费。 平缓的意思是海拔单调增或单调减（非严格，下同），放在《2.3 记...

2014-02-10阅读(5088)评论(0)

POJ 1631 Bridging signals 新来的实习生把路由线路搞得一团糟！如图，原本左右端口应当按顺序连接。现在只有切除部分线路，使得任何线路都不相交。希望你写一个程序计算最后剩下多少线路？ 关键字：最长上升子序列 LIS&nb...

2014-02-10阅读(6870)评论(2)

POJ 1065 Wooden Sticks n根木材长l_i重w_i，前一根木材大于后一根的话要浪费一分钟准备机器，求最省方案？ 关键字：最长下降子序列 LDS 鸽笼原理 《2.3 记录结果再利用的“动态规划” 需稍加思考的题目》 题目的...

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

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

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

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

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

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

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

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

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

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

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

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