文档介绍：ACM 程序设计
信息学院计算机应用系
余腊生
11/12/2017
1
今天,
你了吗?
AC
11/12/2017
2
每周一星(4):
我爱小芳
11/12/2017
3
第五讲
动态规划(2)
(Dynamic programming)
11/12/2017
4
一、HDOJ_1421 搬寝室
Sample Input
2 1 1 3
Sample Output
4
11/12/2017
5
第一感觉:
根据题目的要求,每次提的两个物品重量差越小越好,是不是每次提的物品一定是重量相邻的物品呢?
证明:假设四个从小到大的数:a、b、c、d,只需证明以下表达式成立即可:
(a-b)^2+(c-d)^2< (a-c)^2+(b-d)^2
(a-b)^2+(c-d)^2< (a-d)^2+(b-c)^2
……(略)
11/12/2017
6
预备工作:
排序!
11/12/2017
7
第二感觉:
对于一次操作,显然提的物品重量越接近越好,是不是可以贪心呢?
请思考…
考虑以下情况:
1 4 5 8
什么结论?
11/12/2017
8
详细分析:
从最简单的情况考虑:
2个物品选一对,结论显然
结论?
4个物品选一对?(如何利用前面的知识)
3个物品选一对,…
n个物品选一对,…
最终问题:n个物品选k对,如何?(n>=2k)
11/12/2017
9
本题算法(略):
哪位同学做个陈述?
11/12/2017
10