1、動態(tài)規(guī)劃,山東省青島第二中學(xué) 王若松,1、LIS問題,給出一個長度為n的序列 找出一個最長的遞增的子序列 例如：5 1 2 4 3 Ans = 3 Fi = max(Fj + 1) (Aj Ai) Ans = max(Fi) O(N2),1.1、LIS的快速算法,對于兩個位置i, j 如果Fi = Fj但是Ai Aj 那么i就沒用了！ 我們維護(hù)Gi表示Fx = i，Ax最小的一個x,1.1、LIS的快速算法,此時，計算Fi的方法，找出Ai Ax, Gt = x的一個最大的t 二分查找！ 最后再更新一下G數(shù)組即可 時間復(fù)雜度O(NlogN),1.2、LIS問題變形,給出N個點(diǎn)，找出一些x、y坐標(biāo)

2、同時遞增的點(diǎn)(不要求按照以前的順序)。 例如：(5, 5) (1, 3) (2, 2) (3, 4) Ans：(1, 3) (3, 4) (5, 5),1.2、LIS問題變形,經(jīng)典LIS滿足的條件 i j Ai Aj 這個變形問題的條件 xi xj yi yj 能否類比？,1.2、LIS問題變形,序的應(yīng)用！ 我們按照x坐標(biāo)排序之后，就不用再考慮x坐標(biāo)地增的要求了！ 如何處理y坐標(biāo)？ LIS NlogN,1.2.1、巴比倫塔,有n種石塊，石塊能無限供應(yīng)。每種石塊都是長方體，其中第i種石塊的長、寬、高分別為li、wi、hi。石塊可以旋轉(zhuǎn)，使得其中兩維成為長度和寬度，第三維成為高度。如果要把一個石塊

3、放在另一個石塊上面，必須保證上面石塊的長和寬都分別嚴(yán)格小于下面石塊的長和寬。這意味著，即使兩塊長寬相同的石塊也不能堆砌起來。求最多能用多少個石塊？,1.2.1、巴比倫塔,將(li, wi, hi)拆成(li, wi) (wi, li) (li, hi) (hi, li) (wi, hi) (hi, wi) 轉(zhuǎn)化為1.2,1.2.2、KLO,給N個積木，每個積木上面都有一個數(shù)，所有積木壘成了一個高塔。一個上面寫有數(shù)i的積木的正確位置是這個塔從下往上數(shù)第i個位置。從現(xiàn)有的高塔中移走一些，使得有最多的積木在正確的位置。 N=100000,1.2.2、KLO,最后在正確位置的數(shù)一定是遞增的。 但是一個

4、遞增的序列一定都能在正確的位置？ 不一定！ 考慮1 2 5這個序列。 為什么5不能出現(xiàn)在答案中？ 兩個數(shù)之間必須有足夠的填充用的“廢數(shù)”！,1.2.2、KLO,對于Ai Aj 如果Delta = Ai Aj 必須滿足i, j之間至少有Delta個數(shù)，也就是i j = Ai Aj 變形后得到Ai i = Aj j,1.2.2、KLO,1、i j 2、Ai Aj 3、Ai - i = Aj - j 三個條件！不是LIS問題所能處理的！ 注意2、3已經(jīng)隱含了1！ 把Ai看做x坐標(biāo)，Ai - i看做y坐標(biāo)，套用1.2的算法,1.3 Dilworth定理,最長A子序列=最長B序列劃分 A和B對立 最長不

5、降子序列=最長下降序列劃分 ,1.4、Gift,有N個數(shù)，一次操作指的是把一個數(shù)拿出來然后再放回(放到的位置自己定) 問最少幾次操作可以將序列排序 例如：2 1 3 Ans=1,1.4、Gift,Ans = N LIS的長度！,2、LCS,給兩個字符串，求最長公共子序列 子序列是指的是按照順序依次提取出若干字符 例如 aba aca Ans=aa,2.1、LCS的優(yōu)化,*1、通用算法：復(fù)雜度N*M/64 2、排列LCS？ 給定兩個1.n的排列，求LCS,2.1、LCS的優(yōu)化,1 3 2 2 1 3 Ans = 2 對于每個數(shù)記錄在兩個字符串的出現(xiàn)位置，當(dāng)成點(diǎn)對 (1, 2) (3, 1) (2

6、, 3) 選出最多的x、y坐標(biāo)都遞增的點(diǎn) 1.2！ 時間復(fù)雜度NlogN,2.2、LCS計數(shù)1,問串A的一個子序列，串B的一個子串，兩者相等的有多少 例如：A=abac B = bac Ans=8,2.2、LCS計數(shù)1,Fij表示A串的前i個字符，B串前j的字符的LCS的數(shù)量 Fij= Fi - 1j - 1 (when Ai=Bj), + Fi - 1j,2.2、LCS計數(shù)1,可能的問題？ A可能是空串！ 加一個常數(shù)維表示A串是否已經(jīng)至少取了一個字符,2.2、LCS計數(shù)2,求兩個串LCS的數(shù)量 例如：A=AAB B=AB Ans=2,2.2、LCS計數(shù)2,在經(jīng)典做法的基礎(chǔ)上，加入計數(shù)的部分

7、Gij表示A串前i個，B串前j個，取到Fij的方案數(shù) 考慮Gij的計算,2.2、LCS計數(shù)2,Ai=Bj時 Gij=Gi-1j-1 +Gi-1j (當(dāng)Fi-1j=Fij) +Gij-1 (當(dāng)Fij-1=Fij) AiBj時 Gij=Gi-1j (當(dāng)Fi-1j=Fij) +Gij-1 (當(dāng)Fij-1=Fij),2.2、LCS計數(shù)2,問題？ 如果Ai不等于Bj, Fij = Fi 1j - 1 此時Gi - 1j - 1在Gi - 1j, Gij - 1中被計數(shù)了兩次！ 解決方案？ 如果Ai != Bj, Fij = Fi - 1j - 1 Gij = GI - 1j+Gij - 1 GI - 1

8、j - 1,3.1、背包問題,1、部分背包 2、0/1背包 3、完全背包,3.2、消失之物,給定N個物品。 對于每個物品i，我們要計算出，在不使用這個物品而使用其他N-1個物品的情況下，裝滿j(1=j=M)背包的方案數(shù)。 N, M = 1000,3.2、消失之物,在原問題解法的基礎(chǔ)上，加一個Gij,表示在不用i物品的前提下，裝滿j容量背包的方案數(shù) Gij = Fnj Gij Ai,3.3、Elect,給定N個數(shù)，選出一些，要求他們的和最大。并且刪掉任何一個滯后，其他數(shù)的和不能大于總數(shù)的一半。 N, SUM = 1000,3.3、Elect,第二個條件比較困難 我們發(fā)現(xiàn)：如果最小的數(shù)已經(jīng)滿足這個

9、條件了，其他的數(shù)一定滿足了！ 考慮從大到小做背包！ Ans = Ai + Fi - 1SUM / 2,4、數(shù)位統(tǒng)計,求L.R中的數(shù)量不少于的數(shù)量的數(shù)的個數(shù) 求1.L中的數(shù)量不少于的數(shù)量的數(shù)的個數(shù),4、數(shù)位統(tǒng)計,預(yù)處理 統(tǒng)計Fij 表示長度為i的數(shù)，比多j的數(shù)的數(shù)量 統(tǒng)計Gij 表示長度為i的數(shù)，比多j的數(shù)的數(shù)量(不允許前導(dǎo)零),4、數(shù)位統(tǒng)計,統(tǒng)計過程 R = 987654321 從高到低一位一位統(tǒng)計 800000000-899999999 . 000000000-099999999 900000000-909999999 970000000-979999999 980000000-980999

10、999 986000000-986999999 每一段的統(tǒng)計方法？利用之前的DP！,5、矩陣優(yōu)化遞推式,以Fi = Fi - 1 + Fi - 2為例 1, 1, 2, 3, 5, 8, 13,5、矩陣優(yōu)化遞推式,1、矩陣乘法的定義 兩個N*N的數(shù)組A, B C = A * B 等價于 Cij = Aik * Bkj(1 = k = N) 2、矩陣乘法的計算方式 有結(jié)合律，快速冪,5、矩陣優(yōu)化遞推式,3、矩陣的乘法的實(shí)際意義 一個圖的鄰接矩陣G的K次冪G Gij表示從i到j(luò)，走恰好K條邊的方案數(shù) (注意這里的Gij表示邊的數(shù)量) 4、對應(yīng)序列問題到這個圖論問題 加入個點(diǎn)，一個表示i,一個表示i

11、-1。 考慮走一條邊轉(zhuǎn)移到i+1, i 連邊1-2, 2-2 (Fi+1 = Fi + Fi-1) 連邊2-1 (Fi = Fi),5、矩陣優(yōu)化遞推式,5、細(xì)節(jié)問題 最后的矩陣的意義？ (F1, F2) (F2, F3) (F3, F4) 表示的是這些項跟初始項的關(guān)系 Fn = A11 * F1 + A21 * F2,5、矩陣優(yōu)化遞推式,5、細(xì)節(jié)問題 更加復(fù)雜的遞推式？ Fi =a1*Fi - 1 + a2*Fi - 2 + +c 增加矩陣的大?。?系數(shù)？ 連接多條邊表示！ 常數(shù)項？ 取一個點(diǎn)專門用來記錄常數(shù)！,6、maze,給N*N的迷宮，給出初始點(diǎn)。求走K步以后走出矩陣的方案數(shù)。 N, K = 1000,6、maze,60分做法？ FiXY走i步之后到達(dá)(X, Y)的方案數(shù) 難以優(yōu)化！,6、maze,X，Y坐標(biāo)無關(guān)！ 考慮為在