（lecture07）动态规划(2) ACM课件[精].ppt

第五讲
动态规划(2)
(Dynamic programming)
2/1/2018
1
一、HDOJ_1421 搬寝室
Sample Input
2 1 1 3
Sample Output
4
2/1/2018
2
第一感觉:
根据题目的要求,每次提的两个物品重量差越小越好,是不是每次提的物品一定是重量相邻的物品呢?
证明:假设四个从小到大的数: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
……(略)
2/1/2018
3
预备工作:
排序!
2/1/2018
4
第二感觉:
对于一次操作,显然提的物品重量越接近越好,是不是可以贪心呢?
请思考…
考虑以下情况:
1 4 5 8
什么结论?
2/1/2018
5
本题算法(略):
哪位同学做个陈述?
2/1/2018
7
二、HDOJ_1058 Humble Numbers
Problem Description
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers. Write a program to find and print the nth element in this sequence
2/1/2018
8
思考: 动态规划的特征体现在什么地方?
2/1/2018
9
算法分析:典型的DP!
1 ->?
1 ->2=min(1*2,1*3,1*5,1*7)
1 ->2 ->3=min(2*2,1*3,1*5,1*7)
1 ->2 ->3 -> 4 = min(2*2,2*3,1*5,1*7)
1 ->2 ->3 -> 4 ->5= min(3*2,2*3,1*5,1*7)
2/1/2018
10