lecutre_11_2动态规划（2）.pptVIP

ACM程序设计 杭州电子科技大学 刘春英 acm@hdu.edu.cn 今天， 你开始 了吗？ 本周双星（12）： 第十三讲 动态规划（2） （Dynamic Programming） 第一感觉： 根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？ 预备工作： 排序！ 第二感觉： 对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？ 请思考… 详细分析： 从最简单的情况考虑： 2个物品选一对，结论显然 本题算法(略)： 哪位同学做个陈述？ 思考： 动态规划的特征体现在什么地方？ 算法分析：典型的DP! 状态转移方程？ F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7) (ni,j,k,m) 特别的： i,j,k,m 只有在本项被选中后才移动 2）修改其它各顶点的Dist[k]值。(为什么？) 思考题： 1074_Doing? Homework 思考：如何自顶向下的分析？ ？ 思考：如何自底向上的计算？ ？ 图示说明（假设有3门功课）： 图示说明（假设有4门功课）： 象不象数塔？ 附录：DP练习题(HDOJ)： 1003、1074、1087、1159、1160、1176 1024、1025、1058、1069、1081 1157、1158、1466 1078、1080、1114 1203、1294、1227、1223 1500、1501、1502、1503 1505、1506、1510、2059 最短路径：1142 、1385 、1548 记住: 快乐学习～ 快乐生活～ Welcome to HDOJ Thank You ~ 1 2 3 1,2 2,3 1,3 1,2,3 1 2 3 4 1,2 2,3 1,3 1,4 2,4 3,4 1,2,3 1,2,4 1,3,4 2,3,4 1,2,3,4 * * 复习晓黎 mondayblue 例1: HDOJ_1421 搬寝室 Sample Input 2 1 1 3 Sample Output 4 证明：假设四个从小到大的数：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 ……(略) 考虑以下情况： 1 4 5 8 什么结论？ 结论？ 4个物品选一对？（如何利用前面的知识） 3个物品选一对，… n个物品选一对，… 最终问题：n个物品选k对，如何？（n=2k） n个物品选二对，… 例2: 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 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) 三、经典问题 最短路径问题 V0 V1 V2 V3 V4 V5 100 10 30 10 5 50 20 60 60 (V0,V4,V3,V5) V5 30 (V0,V4) V4 50 (V0,V4,V3) V3 10 （V0,V2） V2 无 V1 V0 路径长度 最短 路径 终点 起点 求最短路径的基本思想: 按照最短路径的长度递增的次序依次求得源点到其余各点的最短路径。 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 路径长度最短的最短路径的特点： 假设，从源点到顶点V1的最短路径是所有最短路径中长度最短者。 路径长度次短的最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。 路径长度第三短的路径特点: 它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由