当前位置:首页 >> 学科竞赛 >>

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


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 111 222 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][j] 表示看护区域[i,j]需要的最小代价 边界:f[Li][Ri]=Ci Min{f[i][t]+Ck} //Lk<=t<=j<=Rk 转移:f[i][j]=Min Min{f[t][j]+Ck} //Lk<=i<=t<=Rk

JSOI2014夏令营

解法三:
f[i]表示在第i座山设置看护点,覆盖区域1~i的最小 费用 边界:f[0]=0; F[i]=Min{f[k]}+c[i] //i>=right[k]>=left[i] 最优解为min{f[i]} //right[i]>=n>=i

JSOI2014夏令营

问题二:幻想(fish2)
【问题描述】 约翰做了个美梦,很开心,便飘飘然了……。他又开始幻想:池塘中的小鱼们生活很有规律,按时同步作 息。每个池塘的上鱼率预先也是已知的,池塘Li在第一个单位时间内能钓到的鱼为Fi(0<=Fi<=100),并且小 鱼醒来后每过一个单位时间在单位时间内能钓到的鱼将减少一个常数di(0<=di<=100)。还有个奇特的现象, 就是小鱼醒来后,只要有人经过池塘,就会全部溜掉。约翰可以趁小鱼睡着时来到其中任意一个池塘,也可以 任选若干个池塘垂钓,并且在每个池塘他都可以呆上任意长的时间,但呆的时间必须为5分钟的倍数,(5分钟 为一个单位时间),已知从池塘Li到池塘Li+1要化去约翰ti个单位时间。 他又来请教你,请你编一个程序来计算最多能钓到多少鱼(h小时内鱼不会睡觉)。 【输入格式】 输入文件中的第一行为一个整数n。 第二行为一个整数h。 第三行为n个用空格隔开的整数,表示Fi(i=1,2,…,n)。 第四行为n个用空格隔开的整数,表示di(i=1,2,…,n)。 第五行为n-1个用空格隔开的整数,表示ti(i=1,2,…,n-1)。 【输出格式】 输出文件中仅一个整数,表示约翰最多能钓到的鱼的数量。 【输入输出样例】 输入: 2 1 10 1 25 2 输出: 30 9

JSOI2014夏令营

分析:

10

JSOI2014夏令营

一种想法:
f[I,j]表示时刻i在池塘j的时候最多能钓到的鱼 边界:f[0,i]=0 转移: f[I,j]=f[i-1,j]+a[j]-b[j]*(i-1)//a[j]-b[j]*(i-1)小于0时算0 f[I,j]=f[i-Dist(j,k),k] //k<>j

JSOI2014夏令营

解法:
阶段: 以每个单位时间作为一个阶段。 状态: F[k,I,j, l]表示第k个单位时间,钓鱼最左边到第i个鱼塘,最 右边到第j个鱼塘,l=1时表示在最左端钓,l=2时表示在 最右端钓。 D[I,k]表示在第i个鱼塘钓第k个5分钟可钓的鱼的个数。 T[i]表示第i-1个鱼塘到第i个鱼塘所需时间。 状态转移方程:(边界、范围) F[0,I,j, 1]=0 F[0,I,j, 2]=0 F[k,I,j, 1]=max(F[k-1,I,j, 1]+D[I,k],F[k-T[I+1], i+1,j,1], F[k-dis[j]+dis[i], i+1,j,2]) F[k,I,j, 2]=max(F[k-1,I,j, 2]+D[j,k],F[k-T[j], i,j-1,2], F[k-dis[j]+dis[i], i,j-1,1])
JSOI2014夏令营

问题三:计划(fish3)
【问题描述】 现实一些吧!真正的钓鱼行动即将开始。约翰计划外出钓鱼h(1<=h<=16)小时,他家附近共有n (2<=n<=25)个池塘,这些池塘分布在一条直线上,约翰将这些池塘按离家的距离编上号,依次为L1,L2,…, Ln,约翰家门外就是第一个池塘,所以他到第一个池塘是不用花时间的,约翰可以任选若干个池塘垂钓,并且 在每个池塘他都可以呆上任意长的时间,但呆的时间必须为5分钟的倍数,(5分钟为一个单位时间),已知从 池塘Li到池塘Li+1要化去约翰ti个单位时间,每个池塘的上鱼率预先也是已知的,池塘Li在第一个单位时间内能 钓到的鱼为Fi(0<=Fi<=100),并且每过一个单位时间在单位时间内能钓到的鱼将减少一个常数di (0<=di<=100)。 现在请你编一个程序来计算约翰最多能钓到多少鱼。 【输入格式】 输入文件中的第一行为一个整数n。 第二行为一个整数h。 第三行为n个用空格隔开的整数,表示Fi(i=1,2,…,n)。 第四行为n个用空格隔开的整数,表示di(i=1,2,…,n)。 第五行为n-1个用空格隔开的整数,表示ti(i=1,2,…,n-1)。 【输出格式】 输出文件中仅一个整数,表示约翰最多能钓到的鱼的数量。 【输入输出样例】 输入: 2 1 10 1 25 2 输出: 31 13

JSOI2014夏令营

分析:

14

JSOI2014夏令营

解法一:
状态: F[I,j,k]表示第j个5分钟在第i个鱼塘钓鱼,且在该鱼塘已钓 了k个5分钟最多钓的鱼的个数。 F[I,j,-1] 表示第j个5分钟在第i个鱼塘钓鱼最多可钓的鱼的个 数(无论在该鱼塘钓多长时间)。 D[I,k]表示在第i个鱼塘钓第k个5分钟可钓的鱼的个数。 T[i]表示第i-1个鱼塘到第i个鱼塘所需时间。 状态转移方程:(边界、范围) F[1,0,0]=0 F[i,j,k]=F[i,j-1,k-1]+D[I,k] //0<k<=j F[I,j,0]=F[I-1,j-T[i],-1] //k=0 F[I,j,-1]=max{F[I,j,k]} //0<=k<=j
JSOI2014夏令营

解法二:
f[i][j]表示在池塘i时刻j最多钓到的鱼 边界:f[1][0]=0 转移:f[i][j]=Max{f[i-1][j-p]+calc(a[i],b[i],p-Dist(i,i1))} //p表示在池塘i钓鱼的时间

JSOI2014夏令营

什么是动态规划?
动态规划是求解包含重叠子问题的最优化方法

动态规划的性质 子问题重叠性质。在用递归算法自顶向下对问题进行求解是,
每次产生的子问题并不总是新问题,有些子问题可能被重复计算多次。 动态规划算法利用此性质,对每个子问题只计算一次,然后将其结果 保存起来以便高效重用。

最优化子结构性质。若问题的最优解所包含的子问题的解也是
最优的,则称该问题具有最优子结构性质(即满足最优化原理) 能用动态规划解决的求最优解问题,必须满足最优解的每个局部也都 是最优的

无后效性。即某阶段的状态一旦确定,则此后过程的演变不再受此
前各状态及决策的影响。也就是说,“未来与过去无关”,当前的状态 是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响 过程未来的演变。
17

JSOI2014夏令营

动态规划算法的步骤:
步骤:动态规划算法的4个步骤: 1. 刻画最优解的结构特性 2. 递归的定义最优解 3. 以自底向上的方法来计算最优解 4. 从计算得到的解来构造一个最优解

18

JSOI2014夏令营

算法模式图
动态规划
多个规划(决策) 当前最优决策 当前非最优决策

规划方向 初始 阶段 当前 阶段i 目标 阶段
i向着目标阶段不断改变(动态)

JSOI2014夏令营

当前阶段的决策仅受前一阶段决策的 影响,并决定下一个阶段的决策

求得的一个最优解

19

程序框架
初始化状态值集合 穷举所有的阶段(for i:=1 to n do) 穷举当前阶段i所有可能的状态j 穷举j状态所有对应的k种子状态进行决策
F[I,j]:=min或max{状态j所有可能的前状态}

输出最优策略
JSOI2014夏令营

20

动态规划常见模型
1D/1D F(i)=min {f(k)+w(k,i)}最长不下降子序列 2D/1D(可优化为1D/1D) fi(j) = min{ fi-1 ( k) + ui (j,k)}

2D/0D F(I,j)=min{f(i-1,j)+f(I,j-1)} F(I,j)=f(i-1,j-1)+w(I,j) 2D/1D F(I,j)=min {f(I,k)+f(k+1,j)}+w(I,j) i<=k<j
21

JSOI2014夏令营

动态规划实例分析
1、金明的预算方案(背包问题拓展) 2、乌龟棋 3、矩阵取数 4、花匠

22

JSOI2014夏令营

金明的预算方案 (NOIP2006)
金明今天很开心,家里购置的新房就要领钥匙了,新房里 有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈 昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了 算,只要不超过N元钱就行”。今天一早,金明就开始做预算了, 他把想买的物品分为两类:主件与附件,附件是从属于某个主 件的,下表就是一些主件与附件的例子: 主件 附件 电脑 打印机,扫描仪 书柜 图书 书桌 台灯,文具 工作椅 无

23

JSOI2014夏令营

如果要买归类为附件的物品,必须先买该附件所属的主件。 每个主件可以有0个、1个或2个附件。附件不再有从属于自己的 附件。金明想买的东西很多,肯定会超过妈妈限定的N元。于是, 他把每件物品规定了一个重要度,分为5等:用整数1~5表示, 第5等最重要。他还从因特网上查到了每件物品的价格(都是10 元的整数倍)。他希望在不超过N元(可以等于N元)的前提下, 使每件物品的价格与重要度的乘积的总和最大。设第j件物品的 价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1, j2,……,jk,则所求的总和为: v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号) 请你帮助金明设计一个满足要求的购物单。

24

JSOI2014夏令营

【输入文件】 输入文件的第1行,为两个正整数,用一个空格隔开: N m 其中N(<32000)表示总钱数,m(<60)为希望购买物品的个 数。)从第2行到第m+1行,第j行给出了编号为j-1的物品的基本 数据,每行有3个非负整数 v p q (其中v表示该物品的价格 (v<10000),p表示该物品的重要度(1~5),q表示该物品是主 件还是附件。如果q=0,表示该物品为主件,如果q>0,表示该物 品为附件,q是所属主件的编号) 【输出文件】 输出文件只有一个正整数,为不超过总钱数的物品的价格与 重要度乘积的总和的最大值 (<200000)。 【输入样例】 【输出样例】 1000 5 2200 800 2 0 400 5 1 300 5 1 400 3 0 JSOI2014 夏令营 500 20

25

分析:
设F(i,j)表示前i件物品背包为j的最优解,则有,
? F ( i ? 1, j ), 不选第 i 件物品 ? ? F ( i ? 1, j ? w [ i ]) ? c [ i ],只选主件 ? F ( i ? 1, j ? w [ i ] - w [ i1]) ? c [ i ] ? c [ i1], ? ? // 选主件和第 1件附件 F ( i , j ) ? Max ? ? F ( i ? 1, j ? w [ i ] - w [ i 2 ]) ? c [ i ] ? c [ i 2 ], ? // 选主件和第 2 件附件 ? ? F ( i ? 1, j ? w [ i ] - w [ i1] - w [ i 2 ]) ? c [ i ] ? c [ i1] ? c [ i 2 ], ? // 选主件和 2 件附件 ?

边界条件:F[0,0]=0 1<=i<=N, 0<=j<=M 时间复杂度O(NM)

26

JSOI2014夏令营

乌龟棋 (NOIP2010)
【问题描述】 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。乌龟棋 的棋盘是一行N 个格子,每个格子上一个分数(非负整数)。棋盘 第1 格是唯一 的起点,第N 格是终点,游戏要求玩家控制一个乌龟 棋子从起点出发走到终点。

……
1 2 3 4 5 ……. N 乌龟棋中M 张爬行卡片,分成4 种不同的类型(M 张卡片中不 一定包含所有4 种类型的卡片,见样例),每种类型的卡片上分别 标有1、2、3、4 四个数字之一,表示使用这种卡片后,乌龟棋子 将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡 片中选择 一张之前没有使用过的爬行卡片,控制乌龟棋子前进相 应的格子数,每张卡片只能使用一次。游戏中,乌龟棋子自动获得 起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该 格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过 程中到过的所有格子的分数总和。
27

JSOI2014夏令营

很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要 找到一种卡 片使用顺序使得最终游戏得分最多。 现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最 多能得到多少分吗? 【输入】 输入文件名tortoise.in。输入文件的每行中两个数之间用一个空格隔开。 第1 行2 个正整数N 和M,分别表示棋盘格子数和爬行卡片数。 第2 行N 个非负整数,a1, a2, ??, aN,其中ai 表示棋盘第i 个格子上的分数。 第3 行M 个整数,b1,b2, ??, bM,表示M 张爬行卡片上的数字。 输入数据保证到达终点时刚好用光M张爬行卡片,即N? 1= 【输出】 输出文件名tortoise.out。 输出只有1 行,1 个整数,表示小明最多能得到的分数。 。

28

JSOI2014夏令营

分析:

29

JSOI2014夏令营

解法:
状态:
F[I,j,k,l]表示第1种卡片用了i张,第2种卡片用了j 张,第3种卡片用了k张,第4种卡片用了l张。 D[i]表示第i个位置的分数。

状态转移方程:(边界、范围)
F[I,j,k,l]=max{F[i-1,j,k,l] (i>1), F[I,j-1,k,l] //j>1, F[I,j,k-1,l](k>1) , F[I,j,k,l-1] //l>1} +D[i*1+j*2+k*3+l*4+1] F[0,0,0,0]=D[1]

JSOI2014夏令营

矩阵取数游戏 (NOIP2007)
【问题描述】 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩 阵中的每个元素aij均为非负整数。游戏规则如下: 1. 每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有 的元素; 2. 每次取走的各个元素只能是该元素所在行的行首或行尾; 3. 每次取数都有一个得分值,为每行取数的得分之和;每行取数的得 分 = 被取走的元素值*2^i,其中i表示第i次取数(从1开始编 号); 4. 游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大 得分。 【输入】输入文件game.in包括n+1行; 第一行为两个用空格隔开的整数n和m。 第2~n+1行为n*m矩阵,其中每行有m个用单个空格隔开 【输出】 输出文件game.out仅包含1行,为一个整数,即输入矩阵取数后的最大 的分。
31

JSOI2014夏令营

【输入输出样例1】 Game.ingame.out2 3 123 3 4 282【输入输出样例1解释】 第1次:第一行取行首元素,第二行取行尾元素,本次的氛 围1*21+2*21=6 第2次:两行均取行首元素,本次得分为2*22+3*22=20 第3次:得分为3*23+4*23=56。总得分为6+20+56=82 【限制】 60%的数据满足:1<=n, m<=30,答案不超过1016 100%的数据满足:1<=n, m<=80,0<=aij<=1000

32

JSOI2014夏令营

分析:

33

JSOI2014夏令营

解法:
由于这题可以一行一做,所以: 状态: F[I,j]表示行首是第i个数,行末是第j个数。 D[i]表示第i个数的分数。 状态转移方程:(边界、范围) F数组初值清零 F[I,j]=max{F[i-1,j]+D[I-1]*2^(n-j+i-1)//i-1>0 ,F[I,j-1]+D[j+1]*2^ (n-j+i-1)//j+1<=n} //i<=j+1

JSOI2014夏令营

[问题描述] 花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越 来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地, 使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比 较别致。 具体而言,栋栋的花的高度可以看成一列整数h1,h2,…,hn。设当一部分 花被移走后,剩下的花的高度依次为g1,g2,…,gn,则栋栋希望下面 两个条件中至少有一个满足: 条件A:对于所有的1<=i<=m/2,有g2i>g2i-1,同时对于所有的 1<=i<=m/2 ,有g2i>g2i+1; 条件B:对于所有的1<=i<=m/2,有g2i<g2i-1,同时对于所有的 1<=i<=m/2 ,有g2i<g2i+1。 注意上面两个条件在m=1时同时满足,当m>1时最多有一个能满足。 请问,栋栋最多能将多少株花留在原地。 问题输入: 输入的第一行包含一个整数n,表示开始时花的株数。 第二行包含n个整数,依次为h1,h2,…,hn,表示每株花的高度。 问题输出: 输出文件一行,包含一个整数m,表示最多能留在原地的花的株数。
35

花匠 (NOIP2013)

JSOI2014夏令营

输入样例: 5 53212 输出样例: 3 【输入输出样例说明】 有多种方法可以正好保留3株花,例如,留下第1、4、5株,高度分别为5、1、 2,满足条件B。 数据限制: 对于20%的数据,n≤10; 对于30%的数据,n≤25; 对于70%的数据,n≤1000,0≤hi≤1000; 对于100%的数据,1≤n≤100,000,0≤hi≤1,000,000,所有的hi随机生成,所 有随机数服从某区间内的均匀分布。

36

JSOI2014夏令营

分析:

37

JSOI2014夏令营

解法:
状态: F[I,1]表示到第i株花为峰时的最大长度。 F[I,2]表示到第i株花为谷时的最大长度。 H[i]表示第i株花的高度。 状态转移方程:(边界、范围) F[1,1]=1 F[1,2]=1 F[0,1]=1 F[0,2]=1 F[I,1]=max{F[j,2]}+1 //0<=j<I,H[i]>H[j] F[I,2]=max{F[j,1]}+1 //0<=j<I,H[i]<H[j]

JSOI2014夏令营

解题过程小结:
? 1、分析最优解的性质,并刻划其结构特征。 ? 2、递归地定义最优值。 (找定量) ? 3、以自底向上的方式或自顶向下的记忆化方法 (备忘录法)计算出最优值。 ? 4、根据计算最优值时得到的信息,构造一个最 优解。

39

JSOI2014夏令营

动态规划实现方法及技巧交流

40

JSOI2014夏令营

谢谢!

41

JSOI2014夏令营


相关文章:
更多相关标签: