posts - 7, comments - 2, trackbacks - 0, articles - 1
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

动态规划专练(不断练习更新中)

Posted on 2009-04-15 00:57 Lemon 阅读(286) 评论(0)  编辑 收藏 引用

1.Tourist http://acm.pku.edu.cn/JudgeOnline/problem?id=2964 做过一道类似的http://acm.hdu.edu.cn/showproblem.php?pid=2686规模小,可以n^4(dp[x1][y1][x2][y2])解决,本题要一个n^3的状态方程.仔细观察n^4的方程,可以发现有很多冗余状态.dp[step][x1][x2], y1 = step - x1, y2 = step - x2.
2.Polygon http://acm.pku.edu.cn/JudgeOnline/problem?id=1179 有一个细节要特别注意,两个很小的负数相乘变成一个很大的正数。枚举第一条要消去的边,再dp[form][to][2],最后一维0记录最小值,1记录最大值,记忆化搜索一下。
3.Milking Time http://acm.pku.edu.cn/JudgeOnline/problem?id=3616 一维dp,按开始时间排序,特殊处理第一段(不用休息),注意时间段,比如r = 2时, [1, 2]和[4, 5]不冲突。
4.Euro Efficiency http://acm.pku.edu.cn/JudgeOnline/problem?id=1252 无穷背包,或最短路搜索。有个细节要注意:一个数可以由超过100的数减另一个数得到。
5.Washing Clothes http://acm.pku.edu.cn/JudgeOnline/problem?id=3211 简单的01背包,每件衣服的时间小于1000,总时间不超过100000,背包分配男生的任务,剩下就是女生的了。


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理