2014信息学奥林匹克夏令营-day3动态规划(荆晓虹).pdf

JSOI2014夏令营 动态规划的应用 主讲：荆晓虹 江苏省丹阳高级中学 2014年7月 内容提要  动态规划常见模型  动态规划实例分析  动态规划实现方法及技巧交流  上机作业 2 JSOI2014夏令营 问题一：美梦 【问题描述】 这天晚上，约翰做了个奇怪的美梦。他拥有了分别分布在N座高高低低的山上的N个池塘，N座山连成一条 直线，从左往右第i座山的高度是Hi 。池塘中的鱼都是他请专家运用科学的方法专门养殖的，为了保护每个池 塘的生态环境，他现在要在这N座山上建造若干个看护点。约翰是个很节约的人，在第i座山建造看护点的花费 为Ci 。假设在第i座山建造一个看护点，则往左或者往右第一座不比这座山低的山将挡住看护的视线。譬如说： {Hi} = {1 4 4 5 7 2}表示第一座山高度为1，第二座山高度为4 。。。 如果在第1座山建造一个看护点，则可以看护第1,2两个池塘。如果在第5座山上建造一个看护点，则左右的池 塘都能被看护到。如果在第3座山上建造一个看护点，则能够看护到第2 ，3，4个池塘。 Problem Task 要求能够看护到所有的池塘，建造看护点的最小代价是多少。即建造看护点的山对应的花费Ci之和最小。 Problem Input 第一行包含一个正整数N ，N满足1=N=1000000。 第二行包含N个正整数，第i个正整数Hi满足1=Hi=10^9，表示第i座山的高度 第三行包含N个正整数，第i个正整数Ci满足1=Ci=10^9 ，表示在第i座山建造看护点的代价为Ci Problem Output 一行包含一个正整数C，表示最小的代价。 Problem Input Example 3 1 1 1 2 2 2 Problem output Example 2 3 JSOI2014夏令营 分析： 4 JSOI2014夏令营 一种想法： f[i]表示看护区域[1,i]需要的最小费用 Li表示第i座山最左边可以覆盖的山。 Ri表示第i座山最右边可以覆盖的山。 边界：f[0]=0; 转移：f[i]=min{ f[Lk-1]+Ck} k=i JSOI2014夏令营 解法一： f[i]表示看护区域[1,i]需要的最小费用 Li表示第i座山最左边可以覆盖的山。 Ri表示第i座山最右边可以覆盖的山。 边界：f[0]=0; 转移：f[i]=min{min{f[t]}+Ck} //Lk=t=k=Rk=i JSOI2014夏令营 解法二： f[i