省选讲课-动规题

动规题选讲浙江省温州中学徐持衡动态规划近年来，涉及动态规划的各种竞赛题越来越多，几乎每一场都会有一两道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。动态规划基本原理多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)。一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。动态规划基本原理各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用一个数值来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。动态规划基本原理如图示，一个带权有向的多段图，要求从A到D的最短路径的长度(下面简称最短距离)动态规划的术语阶段状态无后效性决策策略最优性原理阶段把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。状态状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。状态也就是对当前决策的限制条件。无后效性我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。状态决定了当前决策的限制条件。决策一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。策略由每个阶段的决策组成的序列称为策略。能达到最优效果的可行策略称为最优策略。最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。最优性原理实际上是要求问题的最优策略的子策略也是最优。动规题选讲最优最大最小最长不降子序列给出一个长度为n(n<=100000)的数字序列Xi，求一个最长的子序列，使得这个子序列中的数字依次不降。X132142最长不降子序列f[i]表示第i个数字最多能作为多长的不降子序列的最后一个数字。f[i]=max{f[j]|j<i,Xi>=Xj}O(n2)X153241f122232最长不降子序列f[i]当前可以作为第i个不降子序列的最小值。可以证明f[i]在任意时刻都是不降的。用二分查找，每次找到最后一个f[i]<=Xj，用Xj更新f[i+1]O(nlogn)特殊的最长公共子序列给出两个1到n(n<=100000)的排列，求最长公共子序列。X1123546X2423165特殊的最长公共子序列f[i,j]表示第一个序列的前i个元素和第二个序列的前j个元素的最长公共子序列。X1123546X2423165特殊的最长公共子序列f[i,j]=max{f[i–1,j],f[i,j–1],f[i–1,j–1]+ord(X1[i]=X2[i])}O(n2)X1123546X2423165特殊的最长公共子序列可以把信息转化为求最长不降子序列。同样可以做到O(nlogn)X1123546X2423165F423615二维最长不降子序列给出n(n<=100000)组数(Ai,Bi)，取出最多组，对于任意i<j满足Ai<=Aj,Bi<=Bj二维最长不降子序列O(n2)的算法依然可用。要怎么改造O(nlogn)的算法？二维最长不降子序列本来的f[i]现在对应一棵BST，按Ai排序，删除Ai<=Aj且Bi<=Bj的元素j。凸多边形三角划分给定一个具有N（N<50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？凸多边形三角划分这是一道很典型的动态规划问题。设F[I,J]（I<J）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(I<K<J)目标状态为：F[1,N]目标状态为：F[i,i+n-1]分配方案数有n个不同的东西，分成m份，每份最少min个，求总方案数。(n,m<=1000)每份是相同的。分配方案数f[i,j]表示总共i个分成j份的总方案数。f[i,j]=sum{f[i-k,j-1]*C(i-1,k-1)}(k>=min)枚举k，时间复杂度O(m*n2)分配方案数改变思路，每次处理最小的一个。分为两种情况：在一个大小为min的组里在一个大小大于min的组里分配方案数f[i,j]=f[i-min,j-1]*C(i-1,min-1)

//第一种情况+f[i-1,j]*j//第二种情况O(n*m)交叉匹配现有两行正整数，长度都小于1000。如果第一行中有一个数和第二行中的一个数相同，都为r，则我们可以将这两个数用线段连起来。称这条线段为r－匹配线段。例如下图就显示了一条3匹配线段和一条2匹配线段。交叉匹配每条a匹配线段恰好和一条b匹配线段相交，且a≠b，a,b指代任何值，并非特定值。不存在两条线段都从一个数出发。计算出匹配线段的最多个数。交叉匹配转移时要两对一起转移用f[i,j]表示第一列的前i个和第二列的前j个的最大匹配数。交叉匹配这是一个多次动态规划问题。设这两行数分别保存在a[n]和b[m]中。用f(i,j)表示如下图所示的两行数据，可以画出的最多的匹配线段数。交叉匹配对于这个状态的求解，可以分如下几种情况讨论：1.没有从a[i]出发的匹配线段。如下图，这种情况的解即为f(i–1,j)交叉匹配2.没有从b[j]出发的匹配线段。如下图，这种情况的解即为f(i,j–1)交叉匹配3.a[i]和b[j]处，各引出一条匹配线段，这时必须a[i]≠b[j]。设a[i]=b[v]，b[j]=a[u]。从a[i]向b[v]，b[j]向a[u]各引一条匹配线段，这两条线段必然相交。这种情况的解即为f(u–1,v–1)+2交叉匹配显然，f(i,j)就是上面三种情况中的最优值。因此，我们可以列出状态转移方程：其中交叉匹配如果存在a[u’]=b[j]，且u<u’<i，则用b[j]向a[u’]的匹配线段，代替b[j]向a[u]的匹配线段，所得到的解不会变差。因此，u的选择是越靠后越好。同理，v的选择也是越靠后越好。交叉匹配对于确定的i和j，相应的u和v的值也是确定的，这些值可以预先求出。而求法也是利用动态规划。设相应u和v的值分别为u[i,j]和v[i,j]。交叉匹配所以最后的算法复杂度为O(n*m)整个算法需要先要计算u,v数组，然后再计算f数组。交叉匹配所以最后的算法复杂度为O(n*m)整个算法需要先要计算u,v数组，然后再计算f数组。最大颁奖台在一个矩形的网格区域有一些坏点。I型颁奖台是由三个矩形相接叠成的，不能含有坏点，其中上方和下方的矩形的两侧必须都超出中间的矩形，否则将被误解成T,L,J等字母。例如：最大颁奖台以下三种情况均不合法：矩阵n*m(n,m<=200)求颁奖台的最大面积最大颁奖台先用f1[i,j,k]表示第i行的第j~k列作为图案中第1个矩形的下边界时，所得到的最大面积。再用f2[i,j,k]表示第1个矩形下边界为第i行的[j’,k’](j’<=j且k’>=k)的最大面积。然后用f3[i,j,k]表示第二个矩形……最大颁奖台算法效率O(n*m2)最大权值凸包给出n(n<=200)个点的坐标及其权值，求凸包的点权值和的最大值。最大权值凸包由于要求是凸包，所以需要记录上次的斜率。f[i,j,k]表示凸包的最左边的点为i，目前的最后两个点是j和k，最大的权值和。枚举l，满足j-k-l是凸的，然后转移。最大权值凸包需要O(n4)改变状态表示f[i,j,k]表示起点i，最后一个点是j，接下来一个点可能是k以及在j-k线以下的点。最大权值凸包需要预处理出斜率仅次于j-k边的k-u[j,k]和j-v[j,k]转移的时候f[i,j,k]就只需要更新f[i,j,v[j,k]]和f[i,k,u[j,k]]两个值就可以了O(n3)新汉诺塔n个柱子m个盘子，求把所有的盘子从1号柱子移到n号柱子的最少步数。新汉诺塔用f[i,j]表示i个盘用j个柱子的最少移动次数。f[i,j]=min{f[k,j]*2+f[i-k,j-1]}(i>=k>=0)滑雪路线在一张n*m的地图中，找到一条最长的先降序后升序的路径，要求点不能重复走。地图中的高度为1到n*m整数，每个数只会出现一次。n,m<=50滑雪路线先按高度排序动规，f[i,j](i<j)表示以i为起点，j为终点的一条先递减后递增路径，然后枚举k满足k与i或j相邻，且比i和j都要高，并更新对应的值。土地购买FJ想要购买N个矩阵，给出每个矩阵的长A[i]和宽B[i],FJ一次可以购买一个或多个矩阵,代价是max(A[i])*max(B[i])求购买全部n个矩阵的最小代价土地购买一个显然的结论是，对于一个矩阵，如果它被任意一个矩阵包含，那么可以不用考虑这个矩阵。按A降序排列后，可以得到O(N^2)的动规方程F[N]=min(F[I]+A[I+1]*B[N])土地购买考虑对于刚才的转移，就是枚举最后一段购买的起点。（最后一段购买i到n）如果对于i<j,如果有F[I]+A[I+1]*B[N]<F[j]+A[j+1]*B[N]那么有(F[I]-F[J])<-B[N]*(A[I+1]-A[J+1])除了B[N]其他都是定值，而B[N]也是单调递增的。土地购买单调队列!O(nlogn)货币兑换(NOI07一试)已知未来N天内的A券和B券的价值以及Rate。如果开始时拥有S元钱，那么N天后最多能够获得多少元钱。买入必须满足买入A的数量MA和买入B的数量MB满足：MA:MB=Rate卖出必须同时卖出p%的A券和B券n<=100000所有数均可以为实数。货币兑换(NOI07一试)必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。货币兑换(NOI07一试)用f[i]表示第i天的最多的钱。那么f[i]可以从前i-1天的任意一天全部买入在第i天全部卖出。也可以是从f[i-1]继承而来。O(n2)货币兑换(NOI07一试)如果把每天的钱全都买入AB券那么用X[i]和Y[i]表示第i天的A券和B券数量。把一个个点都画在一个平面坐标系中。货币兑换(NOI07一试)如图所示货币兑换(NOI07一试)最终维护一个斜率递减的剩余点。二分查找最大值出现的斜率。压缩状态的动态规划含义：以一个集合内的元素信息作为状态，状态总数为指数级别的动态规划。特点：1、本身要满足动态规划的性质：

最优性原理、无后效性。2、数据某几维规模比较小。集合型动态规划给定n个点的有向带权图，求一条经过每个点一次的回路，并要求边权和最小。范围n<=15。集合型动态规划显然对于某一个中间状态，影响它的最后结果的仅仅是当前所在点以及之前已经经过的点。而之前的路径行走情况与之后的解无关。状态