动态规划(2).ppt

文档介绍：ACM程序设计
杭州电子科技大学刘春英
******@hdu.
6/29/2018
1
今天,
你开始了吗?
复****br/>6/29/2018
2
本周双星(12):
06092602黄晓黎
mondayblue
6/29/2018
3
第十三讲
动态规划(2)
(Dynamic Programming)
6/29/2018
4
例1: HDOJ_1421 搬寝室
Sample Input
2 1 1 3
Sample Output
4
6/29/2018
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
……(略)
6/29/2018
6
预备工作:
排序!
6/29/2018
7
第二感觉:
对于一次操作,显然提的物品重量越接近越好,是不是可以贪心呢?
请思考…
考虑以下情况:
1 4 5 8
什么结论?
6/29/2018
8
详细分析:
从最简单的情况考虑:
2个物品选一对,结论显然
结论?
4个物品选一对?(如何利用前面的知识)
3个物品选一对,…
n个物品选一对,…
最终问题:n个物品选k对,如何?(n>=2k)
n个物品选二对,…
6/29/2018
9
本题算法(略):
哪位同学做个陈述?
6/29/2018
10