动态规划及其应用(二).

《动态规划及其应用(二).》由会员分享，可在线阅读，更多相关《动态规划及其应用(二).（26页珍藏版）》请在金锄头文库上搜索。

1、动态规划及其应用（二） 清华大学 杨志灿 动态规划术语 阶段 把所求解问题的过程恰当地分成若干个相互联系的阶段，以便于 求解 状态 状态表示每个阶段开始面临的自然状况或客观条件 决策（转移） 一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的 一种选择（行动）称为决策。 边界 转移过程中的初始情况 策略 由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶 段决策过程，可选取的策略有一定的范围限制，这个范围称为允 许策略集合。允许策略集合中达到最优效果的策略称为最优策 略。 动态规划 Dynamic Programming 求解决策过程最优化的数学方法 适用条件 最优化原理（最优子结

2、构性质） 无后效性 子问题的重叠性 范围 因同样有状态、转移方程、无后效性等性质，故将递推等 类型也纳入DP之下 如计算方案数、期望值 拦截导弹 第一问 求LIS（最长上升子序列） 第二问 数列最少能拆成几个上升子序列 NOIP 1999 senior p1 拦截导弹 求LIS（最长上升子序列） 普通DP：O（n2） 二分/数据结构+DP：O（nlogn） 数列最少能拆成几个上升子序列 贪心 每次用“最经济”的系统去打导弹 模拟：O（n2） 数据结构：O（nlogn） 合唱队形 N位同学站成一排，音乐老师要请其中的(N-K)位同学 出列，使得剩下的K位同学排成合唱队形。 合唱队形 设K位同学从

3、左到右依次编号为1，2，K，他们的身高 分别为T1，T2，TK。 则他们的身高满足T1TK(1=i=K)。 已知所有N位同学的身高，最少需要几位同学出列， 可以使得剩下的同学排成合唱队形。 2 = n = 100， 130 = Ti = 230 NOIP 2004 senior p2 合唱队形 一个上升序列接一个下降序列？ 枚举最高点 两端DP fi为1, i中以第i个人作为终点的最长上升子序列 gi为i, n中以第i个人作为起点的最长下降子序列 ans = max fi + gi - 1； i1, n 时间复杂度 普通DP：O（n2） 二分/数据结构+DP：O（nlogn） 金明的预算方案

4、n元钱买物品。物品分为主件和附件两种，每个主件 可以有0个、1个或2个附件，附件不会再有附件。购 买附件必须先购买对应的主件。 每件物品有价值和重要度，最大化购买物品的重要度 之和 n g2 +1； 条件 B：对于所有的i，g2 g2 1，且g2 g2 +1。 请问，栋栋最多能将多少株花留在原地 1 = n = 100,000, 0 = hi hj) fi0 = max(fi0, fj1 + 1); else fi1 = max(fi1, fj0 + 1); O（n2） 用线段树/树状数组加速转移 O（nlogn） 计算拐点个数 O（n） 乌龟棋 乌龟棋的棋盘是一行N个格子，每个格子上一个分数

5、（非 负整数）。棋盘第1格是唯一的起点，第N格是终点。 乌龟棋有M张爬行卡片，分成4种不同的类型。 每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使 用这种卡片后，乌龟棋子将向前爬行相应的格子数。 游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使 用过的爬行卡片，控制乌龟棋子前进相应的格子数。 游戏中，乌龟棋子自动获得起点格子的分数，并且在后续 的爬行中每到达一个格子，就得到该格子相应的分数。 求小明最多能得到多少分 N = 350， M = 120 NOIP2010 senior p2 乌龟棋 Fni1i2i3i4？ 状态数：O（n*304） Fni1i2i3？ 第四种卡片

6、使用数量可以通过格子数和另外三种卡片使用 数量计算得出 状态数：O（n*303） Fi1i2i3i4 格子数可以通过已使用的四种卡片数量计算得出 状态数：O（304） 时间复杂度 O（状态数） 传纸条 n*m格子有权网格，从左上角（1, 1）到右下角（n, m）传两次纸条。 纸条只能向右或向下传 一个格子只能经过一次 两传纸条路径除起点、终点外无交 最大化路径和 n,m = 50 NOIP2008 senior p3 传纸条 双进程动态规划 仅一条路径 fij 两条路径 fiji2j2？ 保证两路径无交： （i, j）和（i2, j2）必须在同一阶段（斜线） 有废状态 fxij 两点分别位于第

7、x斜线第i和第j位置 无废状态 时间复杂度 O（n3） 矩阵取数游戏 对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非 负整数。 1. 每次取数时须从每行各取走一个元素，共n个。m次后 取完矩阵所有元素； 2. 每次取走的各个元素只能是该元素所在行的行首或行尾 ； 3. 每次取数都有一个得分值，为每行取数的得分之和，每 行取数的得分 = 被取走的元素值*2i，其中i表示第i次取 数（从1开始编号）； 4. 游戏结束总得分为m次取数得分之和。 求出给定矩阵的最大得分。 n, m = 80， 0 = aij = 1000 NOIP2007 senior p3 矩阵取数游戏 行与行之间独立

8、相当于n组数据 转化为一维问题 两端取数 任何时候剩余的数都构成一个区间 区间DP fij表示区间i, j的最优解 两种解法 fij = max(ai + 2 * fi+1j, aj + 2 * fij-1); fij = max(ai*2(m-j+i) + fi+1j, aj*2(m-j+i) + fij-1) 上面两种解法的状态分别表示什么？ 时间复杂度：O（n*m2） 过河 青蛙想沿着独木桥从河的一侧跳到另一侧。 由于桥的长度和青蛙一次跳过的距离都是正整数，我们可 以把独木桥上青蛙可能到达的点看成数轴上的一串整点： 0，1，L（其中L是桥的长度）。坐标为0的点表示 桥的起点，坐标为L的点

9、表示桥的终点。 青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃 的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳 到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 给出桥上m个石子的位置。你的任务是确定青蛙要想过河 ，最少需要踩到的石子数。 L = 109，1 = S = T = 10，1 = m = 100 NOIP 2005 senior p2 过河 fi表示跳到位置i至少要踩的石子数 fi = min fi - x + stonei; xS, T ans = min fj; jL, L+T-1 O（L*(t s + 1)） L = 109，m = 100？ 离散化 若两个相邻

10、石子之间的距离大于T，则可以将两者之间的距 离缩短T 为什么不影响答案？ L = O（m * t） 时间复杂度 O（m * t2） 能量项链 火星人的能量项链上有n颗能量珠，能量珠是一颗有 头标记与尾标记的珠子，标记均为正整数 n颗珠子串成一个环，且前一颗珠子的尾标记等于后 一颗珠子的头标记 相邻两颗珠子能聚合成一颗珠子，释放出m*r*n单位 的能量 前一颗珠子头标记为m，尾标记为r 后一颗珠子头标记为r，尾标记为n 聚合后的珠子头标记为m，尾标记为n 给定一个项链，求最大能释放多少能量 n = 100 NOIP 2006 senior p1 能量项链 区间DP 先考虑链上的问题 fij表示区

11、间i, j的珠子能释放出的最大能量值 区间i,j无论如何操作，最后聚合出的珠子的标记是固定的 枚举决策分界点k，区间i,k和区间k+1,j分别聚合成一颗 珠子后，两者再聚合 环上问题 破环成链 等长复制一遍 DP一遍后取最值 相当于枚举断点 时间复杂度 O（n3） 2k进制数 设r是个2k 进制数，并满足以下条件： r至少是个2位的2k 进制数。 作为2k 进制数，除最后一位外，r的每一位严格小于它右 边相邻的那一位。 将r转换为2进制数q后，则q的总位数不超过w。 在这里，正整数k（1k9）和w（kw 30000） 是事先给定的。 满足上述条件的不同的r共有多少个？ NOIP 2006 se

12、nior p4 2k进制数 将r转换为2进制数q后，则q的总位数不超过w。 r的位数最多为w/k (上整除） k不整除w时，r的首位不超过2(w%k) 1 除最后一位外，r的每一位严格小于它右边相邻的那一 位。 fij表示长度为i且最低位不超过j的数的个数 递推方程 fij = fij-1 + fi-1j-1 答案统计 fi2k - 1，i1, w/k （下取整） 枚举最高位x， fw/k2k 1 - x 高精度 加分二叉树 一棵有点权的二叉树 任一棵子树 subtree （也包含 tree 本身）的加分计算方 法如下： subtree 的左子树的加分 subtree 的右子树 的加分 sub

13、tree 的根的分数 叶子的加分就是叶节点本身的权值 给定一棵n节点的二叉树的中序遍历和每个点的权值 求该树的最高加分以及其前序遍历 NOIP 2003 senior p3 加分二叉树 中序遍历？ 若ai为根，则a1.ai-1为ai的左子树，ai+1.an为 ai的右子树 subtree 的左子树的加分 subtree 的右子树的加分 subtree 的根的分数 最优子结构性质 区间DP fij为中序遍历区间i, j中的节点所形成的子树的最高加 分 枚举根k fij = max fik-1 * fk+1j + valuek 时间复杂度 O（n3） Thanks for listening 欢迎提问