当前位置:首页 >> 理学 >>

动态规划例题讲解


动态规划例题讲解

山东师大附中 魏铭

Preview
本节课主要通过几道例题,总揽NOIp中较 常见的动态规划模型,不会过多涉及优化 内容。

Preview
最长上升子序列 内存碎片 背包问题 最长公共子序列 石子合并 括号序列 决斗 三取方格数 选课 贪吃的九头龙

最长上升子序列
给出一个数列{a1,a2,...,an},要求你选出尽量 多的元素,使这些元素按其相对位置单调 递增。 Sample Input 9 589231746 Sample Output 4

最长上升子序列
算法:动态规划 令f[i]表示以ai为结尾的最长上升子序列的长 度 转移方程: f[i]=max(f[j],1<=j<i,a[j]<a[i])+1 时间复杂度:O(N^2)

最长上升子序列
换一种状态表示方法 令f[i]表示长度为i的上升子序列的结尾数字 最小是多少 初始f[0]=-inf,f[i]=inf(inf为无穷大,可取值 为大于任意ai绝对值的一个数字)

最长上升子序列
F[0] 初始 插入a1后 插入a2后 插入a3后 插入a4后 插入a5后 插入a6后 插入a7后 插入a8后 插入a9后 -inf -inf -inf -inf -inf -inf -inf -inf -inf -inf F[1] inf 5 5 5 2 2 1 1 1 1 F[2] inf inf 8 8 8 3 3 3 3 3 F[3] inf inf inf 9 9 9 9 7 4 4 F[4] inf inf inf inf inf inf inf inf inf 6

Sample Input 5 8 9 2 3 1 7 4 6

最长上升子序列
f[]是单调递增的,因为如果有i<j且f[i]>=f[j], 那么f[i]必定可以被f[j]的方案所更新。 每处理到一个ai,我们要找到一个k满足 f[k–1]<ai且f[k]>=ai,并用ai更新f[k],最终 max(k|f[k]!=inf)就是答案。 可以通过二分查找将时间复杂度降至 O(NlogN)

选人
将所有人按照智商排序,以情商为关键字, 求最长上升子序列的长度即可。

内存碎片
N个内存申请请求,申请长度为L[i]的内存 块c[i]次。 当程序申请长度为L的内存时,也可以给它 分配一块长度为L’(L’>L)的更大的内存块。 内存长度种类不超过K。 求最少需要的内存。

内存碎片
Sample Input 32 10 1 11 1 20 1 3个内存申请 最多2种长度 Sample Output 42

方案: 两个11,一个20

内存碎片
算法:动态规划 先将所有L[i]排序。 112344678 222446688 113366688 233377778
这一行是内存申请的长度

这三行是内存分配的可能长度

内存碎片
一种内存长度覆盖的区间必定是连续的, 并且该内存长度等于覆盖区间最后一个内 存申请操作的长度。 令f[i,j]表示考虑完前i个内存申请操作,并且 已经使用完j种内存长度的最少需要的内存。

内存碎片
f[i,j]=min{ f[k,j-1]+ (c[k+1]+c[k+2]+...+c[i])*L[i],0<=k<i} 预处理sc[i]=c[1]+c[2]+...+c[i] f[i,j]=min{ f[k,j-1]+(sc[i]-sc[k])*L[i],0<=k<i)} 时间复杂度O(N^2*K)

0/1背包问题
共有N件物品,每件物品有一定的重量w[i] 和一定的价值v[i],现在我们有一个最大载 重量limit的包,问放入哪些物品能使得总价 值最高? w[i]和v[i]均为整数,N<=100, limit<=10000

0/1背包问题
SampleInput SampleOutput 3 100 1400 30 300 80 1200 10 200 共有3件物品 重量分别为30/80/10 价值分别为300/1200/200 背包最大载重量为100

0/1背包问题
令f[i,j]表示考虑完前i项物品,并且当前背包 承重不大于j的情况下能获得的最大价值 f[i,j]=max( f[i-1,j], //不选第i项物品 f[i-1,j–w[i]]+v[i]) //选择第i项物品 边界条件f[0,i]=0 目标f[n,limit]

0/1背包问题
我们注意到,f[i,j]仅与f[i-1,j]和 f[i-1,j-w[i]]有关,因此没必要保存二维数组 令f[i]表示背包承重不大于i的情况下最大价 值

0/1背包问题
fillchar(f,sizeof(f),0); for i:=1 to n do for j:=limit downto w[i] do f[j] = max(f[j], f[j-w[i]]+v[i]); writeln(f[limit]);

完全背包问题
共有N种物品,每种物品有一定的重量w[i] 和一定的价值v[i],每种物品有无限个。现 在我们有一个最大载重量limit的包,问放入 哪些物品能使得总价值最高? w[i]和v[i]均为整数,N<=100, limit<=10000

完全背包问题
fillchar(f,sizeof(f),0); for i:=1 to n do for j:= w[i] to limit do f[j] = max(f[j], f[j-w[i]]+v[i]); writeln(f[limit]);

多重背包问题
共有N种物品,每种物品有一定的重量w[i] 和一定的价值v[i],每种物品有c[i]个。现在 我们有一个最大载重量limit的包,问放入哪 些物品能使得总价值最高? w[i]和v[i]均为整数,N<=100, limit<=10000

多重背包问题
Sample Input Sample Output 3 100 1700 30 300 2 方案: 80 1200 1 1件物品1 10 200 8 7件物品3 共有3件物品 重量分别为30/80/10 价值分别为300/1200/200 数量分别为2/1/8 背包最大载重量为100

多重背包问题
想法1:把每件物品替换为c[i]件相同的物品, 当做0/1背包处理。
编号 W V 1 30 300 2 30 300 3 80 1200 4 10 200 5 10 200 6 10 200 7 10 200 8 10 200 9 10 200 10 10 200 11 10 200

这是原1号物 这是 品 原2号 物品

这是原3号物品

多重背包问题
想法2:把每件物品按照二进制拆分 1=1 8=1+2+4+1 2=1+1 9=1+2+4+2 3=1+2 10=1+2+4+3 4=1+2+1 ... 5=1+2+2 15=1+2+4+8 6=1+2+3 16=1+2+4+8+1 7=1+2+4 17=1+2+4+8+2

多重背包问题
编号 W V

1 30 300

2 30 300

3 80 1200 这是原2 号物品

4 10 200

5 20 400

6 40 800

7 10 200

这是原1号物品

这是原3号物品

最大伤害
将AT值看做体积,将造成的伤害看做价值。 若先不考虑释放最后一个魔法的冷却时间, 这就是一个完全背包问题。 做完完全背包后,枚举释放的最后一次魔 法是什么和释放最后一次魔法时剩余AT是多 少,判定是否能够释放成功,更新答案。

最大伤害
样例1: 驱动魔法所需耗费AT为16,冷却魔法所耗 费AT为5。 做完背包后,f[21]=100,f[42]=200, f[63]=300,f[84]=400。 枚举释放最后一次魔法剩余AT是多少,比如 枚举到AT=84,84+16=100,所以最后一次 魔法能够释放成功,最大伤害500。

最长公共子序列
求两个字符串的最长公共子序列。 最长公共子序列定义: 如果存在一个严格递增的下标序列 b1,b2,b3,b4....bk,使得所有的Zi = Xbi 那么Z是X 的子序列(注意:子序列和子串不同,子串的下 标必须连续,子序列则可以不连续,但要递增)。 给定两个序列X,Y,如果Z既是X的子序列,也是 Y的子序列,那么Z是X和Y的公共子序列。

最长公共子序列
Sample Input ABCDABA BCABDA Sample Output 5

最长公共子序列
算法:动态规划 f[i,j]表示第一个串的1~i与第二个串的1~j的 最长公共子序列长度。 f[i,j]=max{ f[i-1,j], f[i,j-1], f[i-1,j-1]+1(当Xi=Yj时)}

语音识别
先去掉所有空格。 用f[i,j]表示第一个串匹配到i,第二个串匹配 到j的最小差异。 f[i,j]=min{ f[i-1,j-1]+abs(s1[i]-s2[j]), f[i-1,j]+5, f[i,j-1]+5}

石子合并
N堆石子在操场上排成环状,每次可以合并 相邻的两堆石子,耗费的体力值为两堆石 子数量和,若想将所有石子合并到一堆, 至少耗费多少体力?

石子合并
Sample Input 4 4459 Sample Output 43

石子合并
令f[i,j]表示合并完区间[i..j]耗费的最小体力 f[i,j]=min{f[i,k]+f[k+1,j],i<=k<j} +w[i,j] 环的处理方法:可以将序列复制一份放到 序列后,以样例为例,新序列为4 4 5 9 4 4 5 9,答案为f[1,4],f[2,5],f[3,6],f[4,7]中的最 小值 复杂度O(N^3)

石子合并
四边形不等式 在动态规划中,有一类常见的状态转移方程

对于i<=i'<=j<=j'假如有 w(i,j)+w(i',j')<=w(i',j)+w(i,j') ,那么我们称函数w 满足四边形不等式。

石子合并
定理1:若w满足四边形不等式,则m也满 足四边形不等式,即 m(i,j)+m(i',j')<=m(i',j)+m(i,j') 令s[i,j]表示f[i,j]取得最优值的决策 定理2:若f满足四边形不等式,则s单调, 即s[i,j-1]<=s[i,j]<=s[i+1,j] 证明较复杂,略 于是复杂度成功降到了O(N^2)

括号序列
空序列是规则序列。 如果S是规则序列,那么(S)和[S]也是规则序 列。 如果A和B都是规则序列,那么AB也是规则 序列。 现在给出一些由()[]构成的序列,请添加尽 量少的括号,得到一个规则序列。

括号序列
Sample Input ([(] Sample Output ()[()]

括号序列
情况1:S形如(S’)或[S’] 只需将S’变成规则序列即可

括号序列
情况2:S形如(S’或[S’ 只需将S’变成规则序列后,添加)或]即可。

括号序列
情况3:S形如S’)或S’] 只需将S’变成规则序列后,添加(或(即可。

括号序列
情况4:S可被拆分成两部分S1和S2,只需 将S1和S2分别变成规则序列即可。

括号序列
f[i,j]表示将i..j变成规则序列至少要添加的括 号数。 f[i,j]=min{ f[i+1,j+1], //要求s[i]s[j]为()或[] f[i+1,j]+1, //要求s[i]为(或[ f[i,j-1]+1,//要求s[j]为)或] f[i,k]+f[k+1,j],i<=k<j} 时间复杂度O(N^3)

决斗
N个人排成一圈,他们要决斗N-1场,其中 相邻的两人决斗(即第i个人与第i+1个人决 斗,第N个人与第1个人决斗),死者退出, 最终剩下的人胜利。将任意两个人之间决 斗的输赢情况告诉你,决斗顺序由你安排, 问哪些人可能成为最终的胜利者?

决斗
Sample Input 3 010 001 100 1胜2 2胜3 3胜1 Sample Output 123 若23先决斗,则1胜 若13先决斗,则2胜 若12先决斗,则3胜

决斗
把环复制一份,接到环后面,这样编号为x 的人能胜出的充要条件是他能与自己 “相遇”。 123456 1对应4,2对应5,3对应6 由于2可以胜3,因此2将3淘汰后,2和4会 相遇,又因为1可以胜2,因此1将2淘汰后, 1和4会相遇,所以1可能赢得这场决斗。

决斗
设meet[i,j]表示i和j是否能够相遇。 若存在i<k<j满足meet[i,k] && meet[k,j] && (defeat[i,k] || defeat[j,k]),则meet[i,j]=true, 否则meet[i,j]=false

决斗
for i:=1 to n+n-1 do meet[i,i+1]=true; for l:=3 to n+n do for i:= 1 to n+n-l+1 do begin j:=i+l-1; for k:=i+1 to j-1 do if meet[i,k] and meet[k,j] and (defeat[i,k] or defeat[j,k]) then meet[i,j]=true; end; for i:=1 to n do if meet[i,i+n] then writeln(i);

三取方格数
N*N的方格,每个方格有一定的权值,三个 人从左上角向右下角走,只能向下或向右, 求最大路径和,走过多次的方格权值只计 算一次。

三取方格数
Sample Input 4 1234 2134 1234 1324 Sample Output 39

三取方格数
由于走过多次的方格权值只算一次,因此 贪心不可取。 考虑一个人的情况 f[r,c]=max{f[r’,c’]}+v[r,c] 其中r’c’可以到达rc 由此可以推出三个人的方程 f[r1,c1,r2,c2,r3,c3]= max(f[r1’,c1’,r2’,c2’,r3’,c3’]) +value,这里value视情况而定

三取方格数
时间复杂度为O(N^6),太高! 走了相同步数的人,r+c是相同的。 因此我们可以按斜线划分状态

三取方格数
f[s,r1,r2,r3]表示,三个人的x坐标与y坐标和 为s,并且纵坐标分别为r1,r2,r3时,最 大的路径权值和。 f[s,r1,r2,r3]= max{f[s-1,r1’,r2’,r3’]}+value 其中f[s-1,r1’,r2’,r3’]可以通过一步到达 f[s,r1,r2,r3],value视情况而定 时间复杂度O(N^4)

选课
有N门选修课,每门课程有一门直接的先修 课,课程1没有先修课。 每门选修课有一定的学分,现在要求你选 择M门选修课,使学分总和最大。

选课
Sample Input 43 50 91 11 10 3 Sample Output 16

方案: 选择课程1、3、4。

选课
多叉树转二叉树 左孩子右兄弟
1 1

2

3

2

3 4

4

选课
用f[i,j]表示以i为根的子树中,选择j门课程 能够获得的最大学分数。 f[i,j]=max{ f[left[i],k]+f[right[i],j-k-1]+v[i], f[right[i],j]}

贪吃的九头龙
一棵有边权的树,要求你把每个节点染成 1~M中的某种颜色,要求根节点必须为颜 色1,颜色1的节点数量恰好为K,若某条边 两端节点颜色相同,则这条边的权值计入 答案。问最小权值和是多少?

贪吃的九头龙
颜色虽说有M种,但其实可以分为两类:颜 色1和非颜色1。若M=2,则边两端均为或 均不为颜色1需要计入答案,若M>2,则边 两端均为颜色1需要计入答案,均不为颜色 1的边可以通过交叉染色不计入答案。

贪吃的九头龙
多叉转二叉 左孩子右兄弟 略过

贪吃的九头龙
用f[i,j,k]表示以i为根的子树中,将j个节点染 成颜色1,并且i的父亲颜色为k(k=1表示 染成颜色1,k=0表示染成除颜色1外的其他 颜色)最小权值和。

贪吃的九头龙

谢谢大家
QQ:892493591 E-mail:zbwmqlw@gmail.com blog:http://hi.baidu.com/zbwmqlw 欢迎骚扰


赞助商链接
相关文章:
动态规划习题
动态规划习题_理学_高等教育_教育专区。数学模型 第七章 动态规划 规划问题的最终目的就是确定各决策变量的取值, 以使目标函数达到极大或极小。 在线 性规划和非...
动态规划题目及其代码
动态规划题目及其代码_数学_自然科学_专业资料。动态规划题目及其代码 By LYLtim...0-1背包问题动态规划详解... 4页 免费 [普及组]动态规划经典题... 35页 ...
动态规划典型例题
动态规划典型例题 - 1、单调递增最长子序列 描述 求一个字符串的最长递增子序列的长度 如:dabdbf 最长递增子序列就是 abdf,长度为4 输入 第一行一个整数0<n<...
动态规划例题总结
动态规划例题总结 - DP中的典型例题,包括题目描述,解题思路,DP方程,边界条件……比较全面。
动态规划题目
动态规划题目_金融/投资_经管营销_专业资料。动态规划动态规划专题测试 考试时间:3 小时 题一、递增序列(INCNEASING SEQUENCES) 源程序名 INCSQ.??? (PAS,C,CP...
动态规划例子
动态规划例子_理学_高等教育_教育专区。动态规划例题,手动求解。 有8 万元的投资可以投给 3 个过目,每个项目在不同筒子数额下(以万元为单位)的利润如下表 ...
※动态规划经典教程
动态规划经典教程 - dp经典 包涵所有dp 简单易懂 含大量例题... 动态规划经典教程 Directory 1.1 下降/非降子序列问题: 例题 1 拦截导弹例题二 合唱队形※例题...
动态规划算法举例分析
动态规划算法举例分析 - 动态规划算法 1. 动态规划算法介绍 基本思想是将待求解问题分解成若干子问题,先求解子问题,最后用这些子 问题带到原问题, 与分治算法的...
动态规划0起点基础题目
动态规划0起点基础题目_学科竞赛_高中教育_教育专区。NOIP讲义——动态规划0起点...400 5 300 5 400 3 200 2 【输出样例】 3900 *NOIP2006 年普及组复赛题 ...
算法分析复习题目及答案
算法分析复习题目及答案 - 一、选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法...
更多相关标签: