其他老师讲义

1、Dynamic ProgrammingRujia Liu算法设计动态规划状态状态转移方程决策、(边界条件)、(阶段)最优子结构、无后效性实现: 自底向上递推, 自顶向下的记忆化递归递推: 附加时/空开销小, 可用滚动数组, 好调试*递归: 直观/好写/好想, 只解需要解的东西*递推的两种实现算法设计动态规划最长上升子序列(LIS)/导弹拦截第一问最长公共子序列(LCS)/回文词ioi20001 2 3 4 5 6 71 3 2 4 6 7 8最优排序二叉树. O(n3)背包问题?最优矩阵乘法A * (B * C) * D * E. O(n3)花店IOI99 little flower shop

2、乘积最大. 2000*方格取数. 2000*石子合并. ioi95算法设计动态规划动机线性结构树状数值重复/数值范围n个人,每个数不超过m, nm/2di,j = di-1,j or di-1,j-ai*有向无环图(容易进行状态抽象)Mod 4d1,*:=false;d1,0:=true;for i:=2 to n doFor j:=0 to k-1 do for s:=1 to counti do if di-1, (j-w(I,s) mod k+K) mod k then dI,j:=true;Mod 4状态定义: dI,j=true表示从点1到点i存在一条长度mod k值为j的路d1,*

3、:=false;d1,0:=true;for i:=1 to n-1 dofor j:=0 to k-1 do if dI,j then for s:=1 to counti+1 do di+1, (j+w(i+1,s) mod K := true;dominoAi: 骨牌i上下两数之差DI,j: 前i个骨牌和为j,最少翻几次 -1不可能For i:=1 to n-1For j:=-5*I to 5*I If (dI,j = 0) begin if dI,j di+1,j+ai+1 then / 不翻 di := dI,j; if dI,j+1 di+1, j-ai+1 then /翻 . e

4、nd;D3,5=1, a4=-2, d4,3=1, d4,7=2更新法Ioi96 prefixCouldk=true表示前s的前k位可以被基元覆盖.For i:=1 to n do if couldi then begin for j:=1 to p do / 基元个数 if si+1, i+length(Qp) = Qp then couldi+length(Qp) := true; end;空间问题若内存限制64KCould存不下!算could4时,could3的值不会被再次用到.因此在任意时刻,只需要保留couldi,i+20算到i+1时,couldi没有用了,但需要新记录couldi+

5、21模型中的couldi对应到程序中为d.需要根据当前i和could数组下标j算出d的下标D0.19Couldi.i+19Couldj dj-i错位Could = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9D=4, 5, 6, 7, 8, 9希望: d=5, 6, 7, 8, 9For i:=1 to n do begin if d0 then begin for j:=1 to p do / 基元个数 if si+1, i+length(Qp) = Qp then dlength(Qp) := true; end; for j:=0 to 19 do dj := dj+1;En

6、d;循环队列For i:=1 to n do begin u := queuefront; if u then begin for j:=1 to p do / 基元个数 if si+1, i+length(Qp) = Qp then queue(front + length(Qp) mod 20 := true; end; front := (front + 1) mod 20;End;Stockfi = maxfj * vl/vk是否最优决策可能是 卖 卖 (反证,选更高的一天卖).因此: 一定是买卖交替O(n4)分析最优决策序列的特点优化1分类第i天: 卖,则不用枚举L, 不卖,则直接等

7、于f(i-1)O(n3)分类优化2no no sell no buy no no no sell no no (i)含义改变: 枚举变量j就是最近买的一天O(n2) 只枚举有意义的位置, 或者说把决策划分成等价类优化3令g(i) = 前i个f(j)/v(j+1)的最大值f(1)/v(2), f(2)/v(3), f(3)/v(4), f(4)/v(5), g(i) = maxg(i-1), f(i)/v(i+1)比较复杂的计算项自身用动态规划(递推)计算bitonic从左到右的情形: 排序,顺次连接因为第一个点不能被漏掉, 必须首先走Bitonic: 分两条路第一个点不能漏掉,必须由某一条路首

8、先走为了不重复, 需要记录哪些点走过但: 直接记录是O(2n)设计一个理想情况左边的路在顶点I, 右边的路在定义ji左边都走过, j右边都走过, I, j中间没走过维持理想情况(归纳法)先延伸i, 直到第一次超过j延伸顺序无关, 因此没有漏掉解状态: dI,j,表示两条路的端点分别在I, jfarm状态:取决于现在的位置I, 没有完成的任务集合S状态总数: 7*212=28672两种转移(ok)选一个任务,直接到起点: 12=k(cycle)直接选一条边走: 6=mIOI04-Hermis第k个神仙位置为(pxk, pyk)dI,x,y, 现在该给第i个神仙发信息, 现在在位置(x,y)已经走

9、过的最短路.For i:=1 to n do for x:=1 to w do for y:=1 to h do begin if di,x,y + abs(pxi-x) di+1, pxi, y then if dI,x,y + abs(pyi-y) di+1, x, pyi thenEnd;用等价法证明没有漏掉解, 可以一次走路恰好给一个神仙发信息O(nwh)Hermis(cont.)很多格子实际上是没有必要走的ai,j表示发了前i个神仙,现在在(xi, yj)bi,j表示发了前i个神仙,现在在(xj, yi)O(n2)IOI04-PhidiasdI,j表示长为I,宽为j的块最小浪费的面积

10、,那么di,j = minda, j + di-a, j 0aidI,b + dI, j-b 0bj状态:h*w个,转移O(h+w),总O(hw(h+w)由于每次切割的长或宽一定等于某个piece的长或宽,因此决策数=n*2,总Q), 最优解, 且答案为Q-1(子集/数问题无解)或Q2. 如果选得完选完一定是最优的呢? Yes剩下的排序、贪心In-order给pre-order/post-order traversal，数出in-order的个数根结点一定是pre1左子树的结点集合一共有n种如果左子树结点是pre2k+1，且这k个结点在post里也在右子树结点的左边，则需要把pre2.k+1对应到post2.k+1把prek+2.n对应到postk+2,n总数应是二者乘积记dI,j为把preI,j对应到postI,j有几种方法，则递推公式：di,j = sumdi+2,k*dk+1,j /根正确，结点顺序正确Raucous RockersDi,j,k为前i