其他老師講義

1、Dynamic ProgrammingRujia Liu算法設(shè)計(jì)動(dòng)態(tài)規(guī)劃狀態(tài)狀態(tài)轉(zhuǎn)移方程決策、(邊界條件)、(階段)最優(yōu)子結(jié)構(gòu)、無(wú)后效性實(shí)現(xiàn): 自底向上遞推, 自頂向下的記憶化遞歸遞推: 附加時(shí)/空開銷小, 可用滾動(dòng)數(shù)組, 好調(diào)試*遞歸: 直觀/好寫/好想, 只解需要解的東西*遞推的兩種實(shí)現(xiàn)算法設(shè)計(jì)動(dòng)態(tài)規(guī)劃最長(zhǎng)上升子序列(LIS)/導(dǎo)彈攔截第一問最長(zhǎng)公共子序列(LCS)/回文詞ioi20001 2 3 4 5 6 71 3 2 4 6 7 8最優(yōu)排序二叉樹. O(n3)背包問題?最優(yōu)矩陣乘法A * (B * C) * D * E. O(n3)花店IOI99 little flower shop

2、乘積最大. 2000*方格取數(shù). 2000*石子合并. ioi95算法設(shè)計(jì)動(dòng)態(tài)規(guī)劃動(dòng)機(jī)線性結(jié)構(gòu)樹狀數(shù)值重復(fù)/數(shù)值范圍n個(gè)人,每個(gè)數(shù)不超過m, nm/2di,j = di-1,j or di-1,j-ai*有向無(wú)環(huán)圖(容易進(jìn)行狀態(tài)抽象)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狀態(tài)定義: dI,j=true表示從點(diǎn)1到點(diǎn)i存在一條長(zhǎng)度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上下兩數(shù)之差DI,j: 前i個(gè)骨牌和為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 / 基元個(gè)數(shù) if si+1, i+length(Qp) = Qp then couldi+length(Qp) := true; end;空間問題若內(nèi)存限制64KCould存不下!算could4時(shí),could3的值不會(huì)被再次用到.因此在任意時(shí)刻,只需要保留couldi,i+20算到i+1時(shí),couldi沒有用了,但需要新記錄couldi+

5、21模型中的couldi對(duì)應(yīng)到程序中為d.需要根據(jù)當(dāng)前i和could數(shù)組下標(biāo)j算出d的下標(biāo)D0.19Couldi.i+19Couldj dj-i錯(cuò)位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 / 基元個(gè)數(shù) if si+1, i+length(Qp) = Qp then dlength(Qp) := true; end; for j:=0 to 19 do dj := dj+1;En

6、d;循環(huán)隊(duì)列For i:=1 to n do begin u := queuefront; if u then begin for j:=1 to p do / 基元個(gè)數(shù) 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是否最優(yōu)決策可能是 賣 賣 (反證,選更高的一天賣).因此: 一定是買賣交替O(n4)分析最優(yōu)決策序列的特點(diǎn)優(yōu)化1分類第i天: 賣,則不用枚舉L, 不賣,則直接等

7、于f(i-1)O(n3)分類優(yōu)化2no no sell no buy no no no sell no no (i)含義改變: 枚舉變量j就是最近買的一天O(n2) 只枚舉有意義的位置, 或者說(shuō)把決策劃分成等價(jià)類優(yōu)化3令g(i) = 前i個(gè)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)比較復(fù)雜的計(jì)算項(xiàng)自身用動(dòng)態(tài)規(guī)劃(遞推)計(jì)算bitonic從左到右的情形: 排序,順次連接因?yàn)榈谝粋€(gè)點(diǎn)不能被漏掉, 必須首先走Bitonic: 分兩條路第一個(gè)點(diǎn)不能漏掉,必須由某一條路首

8、先走為了不重復(fù), 需要記錄哪些點(diǎn)走過但: 直接記錄是O(2n)設(shè)計(jì)一個(gè)理想情況左邊的路在頂點(diǎn)I, 右邊的路在定義ji左邊都走過, j右邊都走過, I, j中間沒走過維持理想情況(歸納法)先延伸i, 直到第一次超過j延伸順序無(wú)關(guān), 因此沒有漏掉解狀態(tài): dI,j,表示兩條路的端點(diǎn)分別在I, jfarm狀態(tài):取決于現(xiàn)在的位置I, 沒有完成的任務(wù)集合S狀態(tài)總數(shù): 7*212=28672兩種轉(zhuǎn)移(ok)選一個(gè)任務(wù),直接到起點(diǎn): 12=k(cycle)直接選一條邊走: 6=mIOI04-Hermis第k個(gè)神仙位置為(pxk, pyk)dI,x,y, 現(xiàn)在該給第i個(gè)神仙發(fā)信息, 現(xiàn)在在位置(x,y)已經(jīng)走

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;用等價(jià)法證明沒有漏掉解, 可以一次走路恰好給一個(gè)神仙發(fā)信息O(nwh)Hermis(cont.)很多格子實(shí)際上是沒有必要走的ai,j表示發(fā)了前i個(gè)神仙,現(xiàn)在在(xi, yj)bi,j表示發(fā)了前i個(gè)神仙,現(xiàn)在在(xj, yi)O(n2)IOI04-PhidiasdI,j表示長(zhǎng)為I,寬為j的塊最小浪費(fèi)的面積

10、,那么di,j = minda, j + di-a, j 0aidI,b + dI, j-b 0bj狀態(tài):h*w個(gè),轉(zhuǎn)移O(h+w),總O(hw(h+w)由于每次切割的長(zhǎng)或?qū)捯欢ǖ扔谀硞€(gè)piece的長(zhǎng)或?qū)?因此決策數(shù)=n*2,總Q), 最優(yōu)解, 且答案為Q-1(子集/數(shù)問題無(wú)解)或Q2. 如果選得完選完一定是最優(yōu)的呢? Yes剩下的排序、貪心In-order給pre-order/post-order traversal，數(shù)出in-order的個(gè)數(shù)根結(jié)點(diǎn)一定是pre1左子樹的結(jié)點(diǎn)集合一共有n種如果左子樹結(jié)點(diǎn)是pre2k+1，且這k個(gè)結(jié)點(diǎn)在post里也在右子樹結(jié)點(diǎn)的左邊，則需要把pre2.k+1對(duì)應(yīng)到post2.k+1把prek+2.n對(duì)應(yīng)到postk+2,n總數(shù)應(yīng)是二者乘積記dI,j為把preI,j對(duì)應(yīng)到postI,j有幾種方法，則遞推公式：di,j = sumdi+2,k*dk+1,j /根正確，結(jié)點(diǎn)順序正確Raucous RockersDi,j,k為前i