动态规划基础和建模

动态规划基础和建模第1页，课件共105页，创作于2023年2月动态规划是统筹学的重要内容动态规划是OI的重要内容据不完全统计，每次考试动态规划起码有一道题前言动态规划很重要！第2页，课件共105页，创作于2023年2月这个课件的目的：对动态规划的模型进行了一些总结有部分内容超出了NOIP范围为同学们提供一个刷题的方向请同学们踊跃发言前言第3页，课件共105页，创作于2023年2月阶段状态决策状态转移状态转移方程动态规划的基本概念第4页，课件共105页，创作于2023年2月最优子结构无后效性原则重叠子问题动态规划的基本概念DP是一种记忆化的思想第5页，课件共105页，创作于2023年2月拓展一下：阶段->拓扑序状态->点状态转移->边决策->前驱？DFA？动态规划的基本概念DP是状态空间上的最短（长）路或者可行路第6页，课件共105页，创作于2023年2月实现方式：递推：顺推和逆推记忆化搜索前者灵活，优化方法多后者可以减少不必要节点的计算动态规划的基本概念第7页，课件共105页，创作于2023年2月时间复杂度：状态数*转移费用动态规划的基本概念第8页，课件共105页，创作于2023年2月线性模型区间模型矩形模型树形模型背包模型图状模型SCDP多线程DP多重DP更广泛的动态规划的模型第9页，课件共105页，创作于2023年2月单线问题：上楼梯问题LIS问题乌龟棋诗人小G（简化版）双线问题：LCS问题模糊匹配线性模型第10页，课件共105页，创作于2023年2月Zbwmqlw神犇要上楼梯，他一次可以上一层，也可以上两层。楼梯有n层有多少种上楼梯的方案上楼梯问题第11页，课件共105页，创作于2023年2月N<=10^7？设f[i]表示到第i层得方案数前一步可以上一层也可以上两层F[i]=f[i-1]+f[i-2]N<=10^15？矩阵乘法上楼梯问题第12页，课件共105页，创作于2023年2月给定一个数列{an}，求它的一个子序列{bm}满足b1<b2<b3<…<bm使得m最大N<=10000LIS问题第13页，课件共105页，创作于2023年2月设f[i]表示以i结尾的LIS的长度F[i]=max{f[j]}+1,j<i且a[j]<a[i]时间复杂度？O(n^2)如何优化？LIS问题第14页，课件共105页，创作于2023年2月对于i来说，如果存在一个长度为len的LIS以i结尾，那么也一定存在长度<len的即：满足单调性！设g[i]表示f[j]=i的最小的a[j]二分g[k]>=a[i]的最大的kF[i]=k+1时间复杂度O(nlogn)LIS问题第15页，课件共105页，创作于2023年2月乌龟棋（NOIP2010t）第16页，课件共105页，创作于2023年2月F[i][a][b][c][d]表示到位置i，四种操作分别进行了a,b,c,d次决策有四种时间复杂度：O(nc^4)TLE+MLE乌龟棋第17页，课件共105页，创作于2023年2月乌龟棋第18页，课件共105页，创作于2023年2月一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G对于排版中的每行定义了一个不协调度,为这行的实际长度与行标准长度差值绝对值的P次方，而一个排版的不协调度为所有行不协调度的总和。小G最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。诗人小G（NOI2009）简化版第19页，课件共105页，创作于2023年2月F[i]表示前i句诗的最小不协调度F[i]=min{f[j]+(sum[i]-sum[j]+i-j-L)^p}时间复杂度O(n^2)优化？导数证明四边形不等式，有兴趣的同学自己查阅有关资料诗人小G第20页，课件共105页，创作于2023年2月给定两个字符串s，t求最长公共字串例：abcde和ace的LCS是aceN<=1000LCS问题第21页，课件共105页，创作于2023年2月设f[i][j]表示第一个串到i，第二个串到j的LCSF[i][j]=f[i-1][j-1]+1,s[i]=t[j]=min{f[i-1][j],f[i][j-1]},s[i]!=t[j]时间复杂度O(n^2)LCS问题第22页，课件共105页，创作于2023年2月给定两个字符串s和t，每个字符串有英文字母和*？！组成，*？！的含义分别是：*：匹配一个或多个字符；？：匹配至少一个至多三个字符；！：匹配至少三个字符。问两个字符串是否能够匹配。N<=1000模糊匹配（POJ1229）第23页，课件共105页，创作于2023年2月模糊匹配第24页，课件共105页，创作于2023年2月石子归并回文词决斗问题Blocks区间模型第25页，课件共105页，创作于2023年2月有n堆石子，第i堆重a[i]每次可以合并相邻两堆合并费用为新堆的重量求合并成一堆的最小费用N<=200石子归并第26页，课件共105页，创作于2023年2月合并的费用是一段的和设f[i][j]表示合并i到j的一段F[i][j]=min{f[i][k]+f[k+1][j]}+sum[i][j]时间复杂度O(n^3)石子归并第27页，课件共105页，创作于2023年2月给定一个字符串s，要求添加最少的字符，使得s成为一个回文串。N<=5000回文词（IOI2000）第28页，课件共105页，创作于2023年2月abcba：回文abcbc：不回文F[i][j]表示i到j变成回文的最小代价F[i][j]=f[i+1][j-1],s[i]=s[j]=min{f[i+1][j],f[i][j-1]}+1,s[i]!=s[j]时间复杂度O(n^2)回文词第29页，课件共105页，创作于2023年2月N个人排成一圈，他们要决斗N-1场，其中相邻的两人决斗（即第i个人与第i+1个人决斗，第N个人与第1个人决斗），死者退出，最终剩下的人胜利。将任意两个人之间决斗的输赢情况告诉你，决斗顺序由你安排，问哪些人可能成为最终的胜利者？N<=200决斗问题（POI99）第30页，课件共105页，创作于2023年2月首先把环复制一份接到后面然后一个人获胜就是跟自己相遇Meet[i][j]表示i能j相遇Meet[i][j]=meet[i][k]&&meet[k][j]&&(beat[i][k]||beat[j][k])时间复杂度O(n^3)决斗问题第31页，课件共105页，创作于2023年2月Blocks（POJ1390）第32页，课件共105页，创作于2023年2月我们可以选择保留一部分不消除，而跟前面相同颜色的合并起来一起消除以获得更大的费用，所以再设计状态时，我们需要把后面留下的一起考虑进去。首先我们把相邻的相同颜色的缩成一段，len[i]表示第i段的长度记pre[i]表示第i段往前第一个与i颜色相同的段的编号Blocks第33页，课件共105页，创作于2023年2月设f[i][j][k]表示把从第i段到第j段，最后面有长度为k的与j颜色相同的消去的最大得分F[i][j][k]=max{f[i][j-1][0]+(len[j]+k)^2,f[i][pre[j]][len[j]+k]+f[pre[j]+1][j][0]}记忆化搜索实现效率高Blocks第34页，课件共105页，创作于2023年2月降维拆成链：滑雪子矩形：采油区域行列：棋盘分割对角线：转纸条矩形模型第35页，课件共105页，创作于2023年2月Michael喜欢滑雪这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。滑雪（SHTSC2002）第36页，课件共105页，创作于2023年2月滑雪第37页，课件共105页，创作于2023年2月采油区域（APIO2009）第38页，课件共105页，创作于2023年2月一共只有六种情况：采油区域第39页，课件共105页，创作于2023年2月采油区域第40页，课件共105页，创作于2023年2月采油区域第41页，课件共105页，创作于2023年2月采油区域第42页，课件共105页，创作于2023年2月将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了n-1次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。（每次切割都只能沿着棋盘格子的边进行。）棋盘分割（NOI99）第43页，课件共105页，创作于2023年2月棋盘分割第44页，课件共105页，创作于2023年2月棋盘分割第45页，课件共105页，创作于2023年2月棋盘分割第46页，课件共105页，创作于2023年2月传纸条（NOIP2008T）第47页，课件共105页，创作于2023年2月传纸条第48页，课件共105页，创作于2023年2月传纸条第49页，课件共105页，创作于2023年2月数值分配型：选课，贪吃的九头龙多叉转二叉树形背包位置转移型：CellPhoneNetwork链划分型：树的最长链可转化成区间模型和线性模型：加分二叉树树形模型第50页，课件共105页，创作于2023年2月在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？选课（CTSC99）第51页，课件共105页，创作于2023年2月如果要选课程a必须要选课程b，那么就在a和b之间连边，这样，得到的会是一个森林。于是我们添加一个节点0，学分为0，把这个森林连成树，于是问题就是从一颗n+1个节点的树里选m+1个节点，使得总分最大。这样，点0是必须选的。选课第52页，课件共105页，创作于2023年2月选课第53页，课件共105页，创作于2023年2月传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。有一天，有M个脑袋的九头龙看到一棵长有N个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把N个果子分成M组，每组至少有一个果子，让每个头吃一组。贪吃的九头龙（NOI2002）第54页，课件共105页，创作于2023年2月这M个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好K个果子，而且K个果子中理所当然地应该包括唯一的一个最大的果子。果子由N-1根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。贪吃的九头龙第55页，课件共105页，创作于2023年2月对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。九头龙希望它的“难受值”尽量小，你能帮它算算吗？贪吃的九头龙第56页，课件共105页，创作于2023年2月贪吃的九头龙第57页，课件共105页，创作于2023年2月贪吃的九头龙第58页，课件共105页，创作于2023年2月我们从多叉转二叉的角度来看这道题贪吃的九头龙第59页，课件共105页，创作于2023年2月给定一棵树，求树的最长链树的最长链第60页，课件共105页，创作于2023年2月贪心做法：两次BFS证明树的最长链第61页，课件共105页，创作于2023年2月动态规划：设f[i]表示儿子连上来的最长链，g[i]表示儿子连上来的次长链，h[i]表示父亲来的最长链F[i]=max{f[j]}+1同时更新g[i]H[i]=max{f[p],h[p]}+1,f[p]>f[i]+1=max{g[p],h[p]}+1,f[p]=f[i]+1树的最长链第62页，课件共105页，创作于2023年2月给定一棵树，求树的最小点支配集。N<=10000支配集：点覆盖点CellPhoneNetwork（POJ3659）第63页，课件共105页，创作于2023年2月CellPhoneNetwork第64页，课件共105页，创作于2023年2月CellPhoneNetwork第65页，课件共105页，创作于2023年2月CellPhoneNetwork第66页，课件共105页，创作于2023年2月

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数

若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；

（1）tree的最高加分

（2）tree的前序遍历加分二叉树（NOIP2003）第67页，课件共105页，创作于2023年2月加分二叉树第68页，课件共105页，创作于2023年2月部分背包01背包完全背包多重背包分组背包依赖背包泛化物品背包模型第69页，课件共105页，创作于2023年2月给定一个容量为m的背包和n个物品，每个物品有一个价值v和一个费用w，求在满足容量限制的情况下最大化价值。NPC问题背包问题第70页，课件共105页，创作于2023年2月特点：物品可以任意划分方法：求单位价值，贪心部分背包问题第71页，课件共105页，创作于2023年2月01背包问题第72页，课件共105页，创作于2023年2月空间优化：滚动数组代码：voidZeroOnePack{for(inti=1;i<=n;i++)for(intj=m;j>=cost[i];j--)gmax(f[j],f[j-cost[i]]+value[i]);}01背包问题第73页，课件共105页，创作于2023年2月完全背包问题第74页，课件共105页，创作于2023年2月特点：每类问题有个数限制c[i]基本想法：每类物品的每一个看作一个物品，转化成01背包代码：voidLimitedPack{for(inti=1;i<=n;i++)for(intj=1;j<=limit[i];j++)for(intk=m;k>=cost[i];k--)gmax(f[k],f[k-cost[i]]+value[i]);}多重背包问题第75页，课件共105页，创作于2023年2月优化：二进制拆分原理：2^k能够表示出0~2^(k+1)-1的所有数把c[i]拆成若干2^k相加O(nmlogc)多重背包问题第76页，课件共105页，创作于2023年2月特点：物品被分为很多组，每组之间有限制。假设限制为：每组只能取一个F[i][j]=max{f[i-1][j],f[i-1][j-w[i][k]]+v[i][k]}代码：voidGroupPack{for(inti=1;i<=n;i++)for(intj=m;j>=mincost[i];j--)for(intk=1;k<=cnt[i];k++)if(cost[i][k]<=j)gmax(f[j],f[j-cost[i][k]]+value[i][k];}分组背包问题第77页，课件共105页，创作于2023年2月考试的时候合理分配时间是很重要的，我们应该在同样的时间内尽量得到更多的分数。现在有m道题需要在n分钟内解决，每道题分为p个步骤，每道题的每个步骤都会有不同的分值，所需时间也不尽相同。现在你可以从任意一道题的任意一个步骤开始，如果当前步骤与上一步骤不连续，则需要q分钟的思考时间（每题第一个步骤之前同样需要思考），请确定自己的策略使得获得的分数最高。分配时间（WFTSC2009T）第78页，课件共105页，创作于2023年2月每道题实际上是一个组。我们可以发现，每个步骤选或不选对后面的决策是有影响的，所以我们考虑加一维来区分。设f[i][j][k]表示前i道题的前j个步骤，其中第i道题的第j个步骤被选，在k分钟内解决的最大得分，g[i][j][k]表示前i道题的前j个步骤，其中第i道题的第j个步骤不被选，在k分钟内解决的最大得分，那么：分配时间第79页，课件共105页，创作于2023年2月分配时间第80页，课件共105页，创作于2023年2月

依赖背包问题，顾名思义，就是一些物品可以选要建立在其它一些物品被选的基础之上。这类问题往往是建立在树上的，所以通常也叫树形背包问题。鉴于在树形模型中已经有了比较详细的讨论，这里不再详细展开依赖背包问题第81页，课件共105页，创作于2023年2月泛化物品第82页，课件共105页，创作于2023年2月voidGeneralMatters{for(inti=1;i<=n;i++)for(intj=m;j>=0;j--)for(intk=0;k<=j;k++)gmax(f[j],f[j-k]+cost(i,k));}泛化物品第83页，课件共105页，创作于2023年2月回顾上面的数值分配型的树形动态规划，考虑其中的一个节点i，其子树就相当于一个一个的泛化物品，随着分配给它们的数值的变化，其价值也在不断的变化。由此可见，泛化物品在各个方面都有着很广泛的应用。泛化物品第84页，课件共105页，创作于2023年2月环状：Naptime拓扑图：关键路径一般图模型最优贸易图状模型第85页，课件共105页，创作于2023年2月找一个位置把环拆成链DP把链的首尾接成环枚举首状态环状模型第86页，课件共105页，创作于2023年2月小F同学最近特别累，老是想睡觉小F同学把一天分为n个时段，选择不一定连续的m个时段来睡觉小F同学睡眠质量不好，每次睡觉要花1个时段来进入睡眠每个时段有一个休息值a[i]，如果小F同学选择在[I,j]的时段内睡觉的话，得到的休息就是a[i+1]+…+a[j]，因为时段i被用来进入睡眠了如何选择能够休息的最好？注意天与天是连续的，即这n个时段是一个环Naptime（POJ2228）第87页，课件共105页，创作于2023年2月因为环首尾相接的地方会对结果产生影响，所以要枚举开始的状态，做几遍DP设f[i][j][0]表示前i个时间段睡了j段，第i段不睡的最长时间，f[i][j][1]表示第i段睡的最长时间，那么：f[i][j][0]=max{f[i-1][j][0],f[i-1][j][1]}f[i][j][1]=max{f[i-1][j-1][0],f[i-1][j-1][1]+t[i]}初始时，所有的f=-INF然后枚举第一个时间段睡不睡，分别使f[1][1][1]=1,f[1][0][0]=1，做两次DP内存限制比较紧，要滚动naptime第88页，课件共105页，创作于2023年2月边拓扑排序边DPSCC缩点拓扑图模型第89页，课件共105页，创作于2023年2月给定一个DAG，求从s到t的最长路关键路径第90页，课件共105页，创作于2023年2月设f[i]表示从s到i的最长路径F[i]+dis[i][j]->f[j]拓扑排序的过程中解决关键路径第91页，课件共105页，创作于2023年2月给定一个图，边有的是单向的，有的是双向的有一个水晶球，每个点有一个价格从s出发到t，沿途在某个点买入水晶球，在另一个点卖出显然你要先买入才能卖出最大化收益最优贸易（NOIP2009T）第92页，课件共105页，创作于2023年2月方法一：同一个SCC里的点都可以走到，可以在其中任意一个买，任意一个卖收缩SCC，记录SCC的最大值和最小值F[i]表示到i的最大获利，g[i]表示到i的最小价格，minv[i]表示i所在SCC的最小价格，maxv[i]表示i所在SCC的最大价格G[i]=min{g[j],minv[i]}F[i]=max{f[j],maxv[i]-g[i]}边拓扑排序边做最优贸易第93页，课件共105页，创作于2023年2月方法二：F[i][0]表示到i点，没有水晶球的最大F[i][1]表示到i点，有水晶球的最大F[i][0]=max{f[j][0],f[j][1]+w[i]}f[i][1]=max{f[j][1],-w[i]}前面说过：动态规划是状态图的最短路或最长路嵌套在SPFA算法中，迭代求解最优贸易第94页，课件共105页，创作于2023年2月这类问题在NOIP中一般不会出现，但鉴于在NOIP的模拟题和WFTSC中出现了不止一次，稍微提一下插头DP棋盘DP集合DP状态压缩模型第95页，课件共105页，创作于2023年2月把问题的状态压缩成一个k进制数来表示，利用这个数的每一位反映出来的信息来进行转移问题规模往往特别小状态压缩模型第96页，课件共105页，创作于2023年2月困惑的旅行家（WFTSC2010T）第97页，课件共105页，创作于2023年2月经典的TSP问题最优哈密顿回路设f[i][S]表示当前在i点，经过的点的集合是SF[i][S]=min{f[j][S-{i}]+dis[j][i]}Ans=min{f[i][2^n-1]+dis[i][1]}困惑的旅行家第98页，课件共105页，创作于2023年2月多线程动态规划，顾名