NOIP选手必备-信息学《动态规划》讲解

《NOIP选手必备-信息学《动态规划》讲解》由会员分享，可在线阅读，更多相关《NOIP选手必备-信息学《动态规划》讲解（60页珍藏版）》请在金锄头文库上搜索。

1、动态规划 参与竞赛的同学应由竞争关系和独立关系 你做你的 我干我的 程序和算法互相保密 彼此津津乐道于对方的失败和自己的成功 转向合作学习的关系 通过研讨算法 集中编程 互测数据等互相合作的方式完成学习任务 2 斐波纳契数列F n 3 递归vs动态规划 递归版本 F n 1ifn 0orn 1then2return13else4returnF n 1 F n 2 动态规划 F n 1A 0 A 1 12fori 2tondo3A i A i 1 A i 2 4returnA n 太慢 有效率 算法复杂度是O n 4 方法概要 构造一个公式 它表示一个问题的解是与它的子问题的解相关的公式 E g

2、 F n F n 1 F n 2 为这些子问题做索引 以便它们能够在表中更好的存储与检索 i e 数组array 以自底向上的方法来填写这表格 首先填写最小子问题的解 这就保证了当我们解决一个特殊的子问题时 可以利用比它更小的所有可利用的子问题的解 由于历史原因 我们称这种方法为 动态规划 在上世纪40年代末 计算机普及很少时 这些规划设计是与 列表 方法相关的 5 动态规划算法 算法思想将待求解的问题分解成若干个子问题 并存储子问题的解而避免计算重复的子问题 并由子问题的解得到原问题的解 动态规划算法通常用于求解具有某种最优性质的问题 动态规划算法的基本要素 最优子结构性质和重叠子问题 原理

3、 6 最优子结构性质 问题的最优解包含着它的子问题的最优解 即不管前面的策略如何 此后的决策必须是基于当前状态 由上一次决策产生 的最优决策 重叠子问题 在用递归算法自顶向下解问题时 每次产生的子问题并不总是新问题 有些问题被反复计算多次 对每个子问题只解一次 然后将其解保存起来 以后再遇到同样的问题时就可以直接引用 不必重新求解 原理 7 动态规划 解决问题的基本特征 1 动态规划一般解决最值 最优 最大 最小 最长 问题 2 动态规划解决的问题一般是离散的 可以分解 划分阶段 的 3 动态规划解决的问题必须包含最优子结构 即可以由 n 1 的最优推导出n的最优 原理 8 动态规划算法的4个

4、步骤 1 刻画最优解的结构特性 一维 二维 三维数组 2 递归的定义最优解 状态转移方程 3 以自底向上的方法来计算最优解 4 从计算得到的解来构造一个最优解 解决问题的基本步骤 原理 9 实例 例题一 斐波纳契数列F n 步骤1 用F n 表示在斐波纳契数列中第n个数的值 步骤2 状态转移方程 步骤3 以自底向上的方法来计算最优解 步骤4 在数组中分析构造出问题的解 10 例题二 输入n 求出n 步骤1 用F n 表示n 的值 步骤2 状态转移方程 步骤3 以自底向上的方法来计算最优解 实例 11 例题三 排队买票问题 一场演唱会即将举行 现有n个歌迷排队买票 一个人买一张 而售票处规定 一

5、个人每次最多只能买两张票 假设第i位歌迷买一张票需要时间Ti 1 i n 队伍中相邻的两位歌迷 第j个人和第j 1个人 也可以由其中一个人买两张票 而另一位就可以不用排队了 则这两位歌迷买两张票的时间变为Rj 假如Rj Tj Tj 1 这样做就可以缩短后面歌迷等待的时间 加快整个售票的进程 现给出n Tj和Rj 求使每个人都买到票的最短时间和方法 实例 12 1 2 3 4 5 i i 步骤1 用F i 表示前i个人买票的最优方式 即所需最短时间 现在要决定F i 需要考虑两种情况 1 第i个人的票自己买 2 第i个人的票由第i 1个人买 步骤2 状态转移方程 min 步骤3 以自底向上的方法

6、来计算最优解 13 程序的实现 BuyTicks T R 1n length T 2f 0 03f 1 T 1 4fori 2tondo5f i f i 2 R i 1 6iff i f i 1 T i then7f i f i 1 T i 8returnf 14 实例 例题四 求最长不降子序列 1 问题描述设有一个正整数的序列 b1 b2 bn 对于下标i1 i2 im 若有bi1 bi2 bim则称存在一个长度为m的不下降序列 例如 下列数列13791638243718441921226315对于下标i1 1 i2 4 i3 5 i4 9 i5 13 满足13 16 38 44 63 则存

7、在长度为5的不下降序列 但是 我们看到还存在其他的不下降序列 i1 2 i2 3 i3 4 i4 8 i5 10 i6 11 i7 12 i8 13 满足 7 9 16 18 19 21 22 63 则存在长度为8的不下降序列 问题为 当b1 b2 bn给出之后 求出最长的不下降序列 步骤1 用F i 表示第i项到最后一项最长不下降序列的长度的值 步骤2 状态转移方程 d i 表示数列中第i项的值 步骤3 以自底向上的方法来计算最优解 15 拓展1 拦截导弹 vijos1303 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种导弹拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的

8、高度 但是以后每一发炮弹都不能高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入导弹依次飞来的高度 雷达给出的高度数据是不大于30000的正整数 计算这套系统最多能拦截多少导弹 如果要拦截所有导弹最少要配备多少套这种导弹拦截系统 样例 INPUTOUTPUT389207155300299170158656 最多能拦截的导弹数 2 要拦截所有导弹最少要配备的系统数 16 拓展2 低价购买 低价购买 这条建议是在奶牛股票市场取得成功的一半规则 要想被认为是伟大的投资者 你必须遵循以下的问题建议 低价购买 再低价购买 每次你

9、购买一支股票 你必须用低于你上次购买它的价格购买它 买的次数越多越好 你的目标是在遵循以上建议的前提下 求你最多能购买股票的次数 你将被给出一段时间内一支股票每天的出售价 216范围内的正整数 你可以选择在哪些天购买这支股票 每次购买都必须遵循 低价购买 再低价购买 的原则 写一个程序计算最大购买次数 这里是某支股票的价格清单 日期123456789101112价格686954646864706778629887最优秀的投资者可以购买最多4次股票 可行方案中的一种是 日期25610价格69686462输入第1行 N 1 N 5000 股票发行天数第2行 N个数 是每天的股票价格 输出输出文件仅

10、一行包含两个数 最大购买次数和拥有最大购买次数的方案数 231 当二种方案 看起来一样 时 就是说它们构成的价格队列一样的时候 这2种方案被认为是相同的 17 拓展3 合唱队形 vijis1098 N位同学站成一排 音乐老师要请其中的 N K 位同学出列 使得剩下的K位同学排成合唱队形 合唱队形是指这样的一种队形 设K位同学从左到右依次编号为1 2 K 他们的身高分别为T1 T2 TK 则他们的身高满足T1Ti 1 TK 1 i K 你的任务是 已知所有N位同学的身高 计算最少需要几位同学出列 可以使得剩下的同学排成合唱队形 输入的第一行是一个整数N 2 N 100 表示同学的总数 第一行有n

11、个整数 用空格分隔 第i个整数Ti 130 Ti 230 是第i位同学的身高 厘米 输出包括一行 这一行只包含一个整数 就是最少需要几位同学出列 样例输入8186186150200160130197220 样例输出 4 18 例题五 马拦过河卒 实例 问题描述 如图 A点有一个过河卒 需要走到目标B点 卒行走规则 可以向下 或者向右 同时在棋盘上的任一点有一个对方的马 如上图的C点 该马所在的点和所有跳跃一步可达的点称为对方马的控制点 例如上图C点上的马可以控制9个点 图中的P1 P2 P8和C 卒不能通过对方马的控制点 棋盘用坐标表示 A点 0 0 B点 n m n m为不超过20的整数 并

12、由键盘输入 同样马的位置坐标是需要给出的 约定 CA 同时CB 现在要求你计算出卒从A点能够到达B点的路径的条数 输入 键盘输入B点的坐标 n m 以及对方马的坐标 X Y 不用盘错 输出 屏幕输出一个整数 路径的条数 输入输出样例 输入 6632输出 17 19 步骤1 用F X Y 表示到棋盘上每个阶段 X Y 的路径条数 步骤2 状态转移方程 步骤3 以自底向上的方法来计算最优解 分析 阶段 棋盘上的每个可走的点 每个阶段的求解 F X Y F X 1 Y F X Y 1 其中 F 0 0 1F 0 Y 1F X 0 1 20 例题六 数字三角形问题 1 问题描述设有一个三角形的数塔 顶

13、点结点称为根结点 每个结点有一个整数数值 从顶点出发 可以向左走 也可以向右走 如图10一1所示 问题 当三角形数塔给出之后 找出一条从第一层到达底层的路径 使路径的值最大 若这样的路径存在多条 任意给出一条即可 21 步骤1 二维数组D X y 描述问题 D X y 表示从顶层到达第X层第y个位置的最小路径得分 步骤2 状态转移方程 阶段分析 D 1 1 13到第x层的第y个位置有两种可能 要么走右分支得到 要么走左分支得到 D X y min D X 1 y D X 1 y 1 a X y D 1 1 a 1 1 22 拓展 栈 vijos1122 问题背景 栈是计算机中经典的数据结构 简

14、单的说 栈就是限制在一端进行插入删除操作的线性表 栈有两种最重要的操作 即pop 从栈顶弹出一个元素 和push 将一个元素进栈 宁宁考虑的是这样一个问题 一个操作数序列 从1 2 一直到n 图示为1到3的情况 栈A的深度大于n 现在可以进行两种操作 1 将一个数 从操作数序列的头端移到栈的头端 对应数据结构栈的push操作 2 将一个数 从栈的头端移到输出序列的尾端 对应数据结构栈的pop操作 23 使用这两种操作 由一个操作数序列就可以得到一系列的输出序列 下图所示为由123生成序列231的过程 原始状态如上图所示 24 你的程序将对给定的n 计算并输出由操作数序列1 2 n经过操作可能得

15、到的输出序列的总数 输入格式 输入文件只含一个整数n 1 n 18 输出格式 输出文件只有一行 即可能输出序列的总数目 输入样例 3 输出样例 5 25 例题七 最长公共子序列 一个给定序列的子序列是在该序列中删去若干元素后得到的序列 给定两个序列X和Y 当另一序列Z既是X的子序列又是Y的子序列时 称Z是序列X和Y的公共子序列 最长公共子序列 公共子序列中长度最长的子序列 最长公共子序列问题给定两个序列X x1 x2 xm 和Y y1 y2 yn 找出X和Y的一个最长公共子序列 例如 X A B C B D A B X的子序列 所有X的子集 集合中元素按原来在X中的顺序排列 A B D B C

16、 D B 等等 26 例子 X A B C B D A B X A B C B D A B Y B D C A B A Y B D C A B A B C B A 和 B D A B 都是X和Y的最长公共子序列 长度为4 但是 B C A 就不是X和Y的最长公共子序列 27 穷举法 对于每一个Xm的子序列 验证它是否是Yn的子序列 Xm有2m个子序列每个子序列需要o n 的时间来验证它是否是Yn的子序列 从Yn的第一个字母开始扫描下去 如果不是则从第二个开始运行时间 o n2m 28 给定一个序列Xm x1 x2 xm 我们定义Xm的第i个前缀为 Xi x1 x2 xi i 0 1 2 mc i j 为序列Xi x1 x2 xi 和Yj y1 y2 yj 的最长公共子序列的长度 分析 最优子结构性质 设序列Xm x1 x2 xm 和Yn y1 y2 yn 的一个最长公共子序列为Zk z1 z2 zk 则1 若xm yn 则zk xm yn 且Zk 1是Xm 1和Yn 1的最长公共子序列 2 若xm yn 且zk xm 则Zk是Xm 1和Yn的最长公共子序列 3 若xm yn 且zk y