Posted on 2009-04-15 00:57
Lemon 阅读(276)
评论(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，背包分配男生的任务，剩下就是女生的了。