动态规划基础和建模.ppt

1、动态规划基础和建模,山东省潍坊第一中学 秦政 clavichord,动态规划是统筹学的重要内容 动态规划是OI的重要内容 据不完全统计，每次考试动态规划起码有一道题,前言,动态规划很重要 ！,这个课件的目的： 对动态规划的模型进行了一些总结 有部分内容超出了NOIP范围 为同学们提供一个刷题的方向 请同学们踊跃发言,前言,阶段 状态 决策 状态转移 状态转移方程,动态规划的基本概念,最优子结构 无后效性原则 重叠子问题,动态规划的基本概念,DP是一种记忆化的思想,拓展一下： 阶段 - 拓扑序 状态 - 点 状态转移 - 边 决策 - 前驱？DFA？,动态规划的基本概念,DP是状态空间上的最短（

2、长）路或者可行路,实现方式： 递推：顺推和逆推 记忆化搜索 前者灵活，优化方法多 后者可以减少不必要节点的计算,动态规划的基本概念,时间复杂度： 状态数*转移费用,动态规划的基本概念,线性模型 区间模型 矩形模型 树形模型 背包模型 图状模型 SCDP 多线程DP 多重DP 更广泛的,动态规划的模型,单线问题： 上楼梯问题 LIS问题 乌龟棋 诗人小G（简化版） 双线问题： LCS问题 模糊匹配,线性模型,Zbwmqlw神犇要上楼梯，他一次可以上一层，也可以上两层。 楼梯有n层 有多少种上楼梯的方案,上楼梯问题,N=107？ 设fi表示到第i层得方案数 前一步可以上一层也可以上两层 Fi=fi

3、-1+fi-2 N=1015？ 矩阵乘法,上楼梯问题,给定一个数列an，求它的一个子序列bm 满足b1b2b3bm 使得m最大 N=10000,LIS问题,设fi表示以i结尾的LIS的长度 Fi=maxfj+1,ji且ajai 时间复杂度？O(n2) 如何优化？,LIS问题,对于i来说，如果存在一个长度为len的LIS以i结尾，那么也一定存在长度=ai的最大的k Fi=k+1 时间复杂度O(nlogn),LIS问题,乌龟棋（NOIP2010t）,Fiabcd表示到位置i，四种操作分别进行了a,b,c,d次 决策有四种 时间复杂度：O(nc4) TLE+MLE,乌龟棋,乌龟棋,一首诗包含了若干个

4、句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P 次方，而一个排版的不协调度为所有行不协调度的总和。 小G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。,诗人小G（NO

5、I2009）简化版,Fi表示前i句诗的最小不协调度 Fi=minfj+(sumi-sumj+i-j-L)p 时间复杂度O(n2) 优化？ 导数证明四边形不等式，有兴趣的同学自己查阅有关资料,诗人小G,给定两个字符串s，t 求最长公共字串 例：abcde和ace的LCS是ace N=1000,LCS问题,设fij表示第一个串到i，第二个串到j的LCS Fij=fi-1j-1+1, si=tj =minfi-1j,fij-1, si!=tj 时间复杂度O(n2),LCS问题,给定两个字符串s和t，每个字符串有英文字母和*？！组成，*？！的含义分别是： *：匹配一个或多个字符； ？：匹配至少一个至多

6、三个字符； ！：匹配至少三个字符。 问两个字符串是否能够匹配。 N=1000,模糊匹配（POJ1229）,模糊匹配,石子归并 回文词 决斗问题 Blocks,区间模型,有n堆石子，第i堆重ai 每次可以合并相邻两堆 合并费用为新堆的重量 求合并成一堆的最小费用 N=200,石子归并,合并的费用是一段的和 设fij表示合并i到j的一段 Fij=minfik+fk+1j+sumij 时间复杂度O(n3),石子归并,给定一个字符串s，要求添加最少的字符，使得s成为一个回文串。 N=5000,回文词（IOI2000）,abcba：回文 abcbc：不回文 Fij表示i到j变成回文的最小代价 Fij=f

7、i+1j-1, si=sj =minfi+1j,fij-1+1, si!=sj 时间复杂度O(n2),回文词,N个人排成一圈，他们要决斗N-1场，其中相邻的两人决斗（即第i个人与第i+1个人决斗，第N个人与第1个人决斗），死者退出，最终剩下的人胜利。将任意两个人之间决斗的输赢情况告诉你，决斗顺序由你安排，问哪些人可能成为最终的胜利者？ N=200,决斗问题（POI99）,首先把环复制一份接到后面 然后一个人获胜就是跟自己相遇 Meetij表示i能j相遇 Meetij=meetik i=costi;j-) gmax(fj,fj-costi+valuei); ,01背包问题,完全背包问题,特点：每

8、类问题有个数限制ci 基本想法：每类物品的每一个看作一个物品，转化成01背包 代码： void LimitedPack for(int i=1;i=costi;k-) gmax(fk,fk-costi+valuei); ,多重背包问题,优化： 二进制拆分 原理：2k能够表示出02(k+1)-1的所有数 把ci拆成若干2k相加 O(nmlogc),多重背包问题,特点：物品被分为很多组，每组之间有限制。 假设限制为：每组只能取一个 Fij=maxfi-1j,fi-1j-wik+vik 代码： void GroupPack for(int i=1;i=mincosti;j-) for(int k=1

9、;k=cnti;k+) if(costik=j) gmax(fj,fj-costik+valueik; ,分组背包问题,考试的时候合理分配时间是很重要的，我们应该在同样的时间内尽量得到更多的分数。现在有m道题需要在n分钟内解决，每道题分为p个步骤，每道题的每个步骤都会有不同的分值，所需时间也不尽相同。现在你可以从任意一道题的任意一个步骤开始，如果当前步骤与上一步骤不连续，则需要q分钟的思考时间（每题第一个步骤之前同样需要思考），请确定自己的策略使得获得的分数最高。,分配时间（WFTSC2009T）,每道题实际上是一个组。 我们可以发现，每个步骤选或不选对后面的决策是有影响的，所以我们考虑加一维

10、来区分。 设fijk表示前i道题的前j个步骤，其中第i道题的第j个步骤被选，在k分钟内解决的最大得分，gijk表示前i道题的前j个步骤，其中第i道题的第j个步骤不被选，在k分钟内解决的最大得分，那么：,分配时间,分配时间,依赖背包问题，顾名思义，就是一些物品可以选要建立在其它一些物品被选的基础之上。这类问题往往是建立在树上的，所以通常也叫树形背包问题。鉴于在树形模型中已经有了比较详细的讨论，这里不再详细展开,依赖背包问题,泛化物品,void GeneralMatters for(int i=1;i=0;j-) for(int k=0;k=j;k+) gmax(fj,fj-k+cost(i,k)

11、; ,泛化物品,回顾上面的数值分配型的树形动态规划，考虑其中的一个节点i，其子树就相当于一个一个的泛化物品，随着分配给它们的数值的变化，其价值也在不断的变化。由此可见，泛化物品在各个方面都有着很广泛的应用。,泛化物品,环状： Naptime 拓扑图： 关键路径 一般图模型 最优贸易,图状模型,找一个位置把环拆成链 DP 把链的首尾接成环 枚举首状态,环状模型,小F同学最近特别累，老是想睡觉 小F同学把一天分为n个时段，选择不一定连续的m个时段来睡觉 小F同学睡眠质量不好，每次睡觉要花1个时段来进入睡眠 每个时段有一个休息值ai，如果小F同学选择在I,j的时段内睡觉的话，得到的休息就是ai+1+

12、aj，因为时段i被用来进入睡眠了 如何选择能够休息的最好？ 注意天与天是连续的，即这n个时段是一个环,Naptime（POJ2228）,因为环首尾相接的地方会对结果产生影响，所以要枚举开始的状态，做几遍DP 设fij0表示前i个时间段睡了j段，第i段不睡的最长时间，fij1表示第i段睡的最长时间，那么： fij0=maxfi-1j0,fi-1j1 fij1=maxfi-1j-10,fi-1j-11+ti 初始时，所有的f=-INF 然后枚举第一个时间段睡不睡，分别使f111=1,f100=1，做两次DP 内存限制比较紧，要滚动,naptime,边拓扑排序边DP SCC缩点,拓扑图模型,给定一个

13、DAG，求从s到t的最长路,关键路径,设fi表示从s到i的最长路径 Fi+disij-fj 拓扑排序的过程中解决,关键路径,给定一个图，边有的是单向的，有的是双向的 有一个水晶球，每个点有一个价格 从s出发到t，沿途在某个点买入水晶球，在另一个点卖出 显然你要先买入才能卖出 最大化收益,最优贸易（NOIP2009T）,方法一： 同一个SCC里的点都可以走到，可以在其中任意一个买，任意一个卖 收缩SCC，记录SCC的最大值和最小值 Fi表示到i的最大获利，gi表示到i的最小价格，minvi表示i所在SCC的最小价格，maxvi表示i所在SCC的最大价格 Gi=mingj,minvi Fi=max

14、fj,maxvi-gi 边拓扑排序边做,最优贸易,方法二： Fi0表示到i点，没有水晶球的最大 Fi1表示到i点，有水晶球的最大 Fi0=maxfj0,fj1+wi fi1=maxfj1,-wi 前面说过：动态规划是状态图的最短路或最长路 嵌套在SPFA算法中，迭代求解,最优贸易,这类问题在NOIP中一般不会出现，但鉴于在NOIP的模拟题和WFTSC中出现了不止一次，稍微提一下 插头DP 棋盘DP 集合DP,状态压缩模型,把问题的状态压缩成一个k进制数来表示，利用这个数的每一位反映出来的信息来进行转移 问题规模往往特别小,状态压缩模型,困惑的旅行家（WFTSC2010T）,经典的TSP问题 最

15、优哈密顿回路 设fiS表示当前在i点，经过的点的集合是S FiS=minfjS-i+disji Ans=minfi2n-1+disi1,困惑的旅行家,多线程动态规划，顾名思义，就是很多条线一起进行的动态规划。这类问题要完整的表达出各条线的特点，转移往往比较简单。,多线程动态规划,一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工），某一时刻只有一个员工能移动。被请求后，他才能移动，不允许在同样的位置出现两个员工。从p到q移动一个员工，需要花费c(p,q)。这个函数没有必要对称，但是c(p,p)=0。公司必须满足所有 的请求。目标是最小化公司花费。,Mobile Service（tyvj1061）,Fabc表示三个员工分别在a,b,c位置上 Fabc-fqbc+caq -faqc+cbq -fabq+ccq F123=0,Mobile Service,你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。每个城市只能访问一次，除了旅行开始的城市之外，这个城市必定要被访问两次（在旅行的开始和结束）。你不允许使用其他公司的航线或者用其他的交通工具。 给出这个航空公司开放的城市的列表，和两两城市之间