
POJ 3666 Making the Grade 题解 《挑战程序设计竞赛(第2版)》
POJ 3666 Making the Grade 农夫约翰想修一条尽量平缓的路,路的每一段海拔是A_i,修理后是B_i,花费|A_i – B_i|,求最小花费。 平缓的意思是海拔单调增或单调减(非严格,下同),放在《2.3 记...
POJ 3666 Making the Grade 农夫约翰想修一条尽量平缓的路,路的每一段海拔是A_i,修理后是B_i,花费|A_i – B_i|,求最小花费。 平缓的意思是海拔单调增或单调减(非严格,下同),放在《2.3 记...
POJ 1631 Bridging signals 新来的实习生把路由线路搞得一团糟!如图,原本左右端口应当按顺序连接。现在只有切除部分线路,使得任何线路都不相交。希望你写一个程序计算最后剩下多少线路? 关键字:最长上升子序列 LIS&nb...
POJ 1065 Wooden Sticks n根木材长l_i重w_i,前一根木材大于后一根的话要浪费一分钟准备机器,求最省方案? 关键字:最长下降子序列 LDS 鸽笼原理 《2.3 记录结果再利用的“动态规划” 需稍加思考的题目》 题目的...
谈起日语输入法,谷歌日语输入法最好用。我使用过很多输入法,ATOK笨重且收费、微软日语输入法不够智能、百度日语输入法除了卖萌之外一无是处(很多汉字打不出来)。 谷歌日语输入法的安装采取了【下载800kb的引导程序】–【二次下载真...
POJ 3181 Dollar Dayz 农夫约翰有N元钱,市场上有价值1……K的商品无限个,求所有的花钱方案? 这是一个完全背包问题和大数的混合题目。 《2.3 记录结果再利用的“动态规划” 优化递推关系式》练习题的第三题。 定义&nbs...
POJ 3046 Ant Counting 蚂蚁牙黑,蚂蚁牙红:有A只蚂蚁,来自T个家族。同一个家族的蚂蚁长得一样,但是不同家族的蚂蚁牙齿颜色不同。任取n只蚂蚁(S<=n<=B),求能组成几种集合? 这是《2.3 记录结果再利用...
POJ 1742 Coins 传说中的男人八题,是男人就A这八题。有n种面额的硬币,面额个数分别为A_i、C_i,求最多能搭配出几种不超过m的金额? 这是一个多重部分和问题(多重背包问题),放在了《2.3 记录结果再利用的“动态规划” 优化...
2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 3280 Cheapest Palindrome 字串S长M,由N个小写字母构成。欲通过增删字母将其变为回文串,增删特定字母花费不同,求最小花费。 定义dp[i][j]表示将...
2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 3616 Milking Time 奶牛Bessie在0~N时间段产奶。农夫约翰有M个时间段可以挤奶,时间段f,t内Bessie能挤到的牛奶量e。奶牛产奶后需要休息R小时才能...
2.3 记录结果再利用的“动态规划” 基础的动态规划算法 POJ 2385 Apple Catching 2棵苹果树在T分钟内随机由某一棵苹果树掉下一个苹果,奶牛站在树#1下等着吃苹果,它最多愿意移动W次,问它最多能吃到几个苹果。 定义dp...