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

2、：(5, 5) (1, 3) (2, 2) (3, 4)Ans：(1, 3) (3, 4) (5, 5)1.2、LIS問題變形經(jīng)典LIS滿足的條件i jAi Aj這個(gè)變形問題的條件xi xjyi yj能否類比？1.2、LIS問題變形序的應(yīng)用！我們按照x坐標(biāo)排序之后，就不用再考慮x坐標(biāo)地增的要求了！如何處理y坐標(biāo)？LISNlogN1.2.1、巴比倫塔有n種石塊，石塊能無限供應(yīng)。每種石塊都是長方體，其中第i種石塊的長、寬、高分別為li、wi、hi。石塊可以旋轉(zhuǎn)，使得其中兩維成為長度和寬度，第三維成為高度。如果要把一個(gè)石塊放在另一個(gè)石塊上面，必須保證上面石塊的長和寬都分別嚴(yán)格小于下面石塊的長和寬。這

3、意味著，即使兩塊長寬相同的石塊也不能堆砌起來。求最多能用多少個(gè)石塊？1.2.1、巴比倫塔將(li, wi, hi)拆成(li, wi) (wi, li) (li, hi) (hi, li) (wi, hi) (hi, wi)轉(zhuǎn)化為1.21.2.2、KLO給N個(gè)積木，每個(gè)積木上面都有一個(gè)數(shù)，所有積木壘成了一個(gè)高塔。一個(gè)上面寫有數(shù)i的積木的正確位置是這個(gè)塔從下往上數(shù)第i個(gè)位置。從現(xiàn)有的高塔中移走一些，使得有最多的積木在正確的位置。 N Aj如果Delta = Ai Aj必須滿足i, j之間至少有Delta個(gè)數(shù)，也就是i j = Ai Aj變形后得到Ai i j2、Ai Aj3、Ai - i = A

4、j - j三個(gè)條件！不是LIS問題所能處理的！注意2、3已經(jīng)隱含了1！把Ai看做x坐標(biāo)，Ai - i看做y坐標(biāo)，套用1.2的算法1.3 Dilworth定理最長A子序列=最長B序列劃分A和B對(duì)立最長不降子序列=最長下降序列劃分1.4、Gift有N個(gè)數(shù)，一次操作指的是把一個(gè)數(shù)拿出來然后再放回(放到的位置自己定)問最少幾次操作可以將序列排序例如：2 1 3Ans=11.4、GiftAns = N LIS的長度！2、LCS給兩個(gè)字符串，求最長公共子序列子序列是指的是按照順序依次提取出若干字符例如 aba acaAns=aa2.1、LCS的優(yōu)化*1、通用算法：復(fù)雜度N*M/642、排列LCS？給定兩個(gè)

5、1.n的排列，求LCS2.1、LCS的優(yōu)化1 3 22 1 3對(duì)于每個(gè)數(shù)記錄在兩個(gè)字符串的出現(xiàn)位置，當(dāng)成點(diǎn)對(duì)(1, 2) (3, 1) (2, 3)選出最多的x、y坐標(biāo)都遞增的點(diǎn)1.2！時(shí)間復(fù)雜度NlogN2.2、LCS計(jì)數(shù)1問串A的一個(gè)子序列，串B的一個(gè)子串，兩者相等的有多少例如：A=abac B = bacAns=82.2、LCS計(jì)數(shù)1Fij表示A串的前i個(gè)字符，B串前j的字符的LCS的數(shù)量Fij= Fi - 1j - 1 (when Ai=Bj), + Fi - 1j2.2、LCS計(jì)數(shù)1可能的問題？A可能是空串！加一個(gè)常數(shù)維表示A串是否已經(jīng)至少取了一個(gè)字符2.2、LCS計(jì)數(shù)2求兩個(gè)串LC

6、S的數(shù)量例如：A=AAB B=ABAns=22.2、LCS計(jì)數(shù)2在經(jīng)典做法的基礎(chǔ)上，加入計(jì)數(shù)的部分Gij表示A串前i個(gè)，B串前j個(gè)，取到Fij的方案數(shù)考慮Gij的計(jì)算2.2、LCS計(jì)數(shù)2Ai=Bj時(shí)Gij=Gi-1j-1 +Gi-1j (當(dāng)Fi-1j=Fij) +Gij-1 (當(dāng)Fij-1=Fij)AiBj時(shí)Gij=Gi-1j (當(dāng)Fi-1j=Fij) +Gij-1 (當(dāng)Fij-1=Fij)2.2、LCS計(jì)數(shù)2問題？如果Ai不等于Bj, Fij = Fi 1j - 1此時(shí)Gi - 1j - 1在Gi - 1j, Gij - 1中被計(jì)數(shù)了兩次！解決方案？如果Ai != Bj, Fij = Fi

7、- 1j - 1Gij = GI - 1j+Gij - 1 GI - 1j - 13.1、背包問題1、部分背包2、0/1背包3、完全背包3.2、消失之物給定N個(gè)物品。對(duì)于每個(gè)物品i，我們要計(jì)算出，在不使用這個(gè)物品而使用其他N-1個(gè)物品的情況下，裝滿j(1=j=M)背包的方案數(shù)。N, M = 10003.2、消失之物在原問題解法的基礎(chǔ)上，加一個(gè)Gij,表示在不用i物品的前提下，裝滿j容量背包的方案數(shù)Gij = Fnj Gij Ai3.3、Elect給定N個(gè)數(shù)，選出一些，要求他們的和最大。并且刪掉任何一個(gè)滯后，其他數(shù)的和不能大于總數(shù)的一半。N, SUM = 10003.3、Elect第二個(gè)條件比較

8、困難我們發(fā)現(xiàn)：如果最小的數(shù)已經(jīng)滿足這個(gè)條件了，其他的數(shù)一定滿足了！考慮從大到小做背包！Ans = Ai + Fi - 1SUM / 24、數(shù)位統(tǒng)計(jì)求L.R中的數(shù)量不少于的數(shù)量的數(shù)的個(gè)數(shù)求1.L中的數(shù)量不少于的數(shù)量的數(shù)的個(gè)數(shù)4、數(shù)位統(tǒng)計(jì)預(yù)處理統(tǒng)計(jì)Fij 表示長度為i的數(shù)，比多j的數(shù)的數(shù)量統(tǒng)計(jì)Gij 表示長度為i的數(shù)，比多j的數(shù)的數(shù)量(不允許前導(dǎo)零)4、數(shù)位統(tǒng)計(jì)統(tǒng)計(jì)過程R = 987654321從高到低一位一位統(tǒng)計(jì)800000000-899999999.000000000-099999999900000000-909999999970000000-979999999980000000-980999999986000000-986999999每一段的統(tǒng)計(jì)方法？利用之前的DP！5、矩陣優(yōu)化遞推式以Fi = Fi - 1 + Fi - 2為例1, 1, 2, 3, 5, 8, 135、矩陣優(yōu)化遞推式1、矩陣乘法的定義兩個(gè)N*N的數(shù)組A, BC = A * B等價(jià)于Cij = Aik * Bkj(1 = k 2, 2-2 (Fi+1 = Fi + Fi-1)連邊2-1 (Fi = Fi)5、矩陣優(yōu)化遞推式5、細(xì)節(jié)問題最后的矩陣的意義？(F1, F2)(F2,