夏令營評測包提高二課件

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

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

3、意味著，即使兩塊長寬相同的石塊也不能堆砌起來。求最多能用多少個石塊？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個積木，每個積木上面都有一個數(shù)，所有積木壘成了一個高塔。一個上面寫有數(shù)i的積木的正確位置是這個塔從下往上數(shù)第i個位置。從現(xiàn)有的高塔中移走一些，使得有最多的積木在正確的位置。 N Aj如果Delta = Ai Aj必須滿足i, j之間至少有Delta個數(shù)，也就是i j = Ai Aj變形后得到Ai i j2、Ai Aj3、Ai - i = A

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

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

6、S的數(shù)量例如：A=AAB B=ABAns=22.2、LCS計數(shù)2在經(jīng)典做法的基礎(chǔ)上，加入計數(shù)的部分Gij表示A串前i個，B串前j個，取到Fij的方案數(shù)考慮Gij的計算2.2、LCS計數(shù)2Ai=Bj時Gij=Gi-1j-1 +Gi-1j (當Fi-1j=Fij) +Gij-1 (當Fij-1=Fij)AiBj時Gij=Gi-1j (當Fi-1j=Fij) +Gij-1 (當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

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

8、困難我們發(fā)現(xiàn)：如果最小的數(shù)已經(jīng)滿足這個條件了，其他的數(shù)一定滿足了！考慮從大到小做背包！Ans = Ai + Fi - 1SUM / 24、數(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-099999999900000000-909999999970000000-979999999980000000-980999999986000000-986999999每一段的統(tǒng)計方法？利用之前的DP！5、矩陣優(yōu)化遞推式以Fi = Fi - 1 + Fi - 2為例1, 1, 2, 3, 5, 8, 135、矩陣優(yōu)化遞推式1、矩陣乘法的定義兩個N*N的數(shù)組A, BC = A * B等價于Cij = Aik * Bkj(1 = k 2, 2-2 (Fi+1 = Fi + Fi-1)連邊2-1 (Fi = Fi)5、矩陣優(yōu)化遞推式5、細節(jié)問題最后的矩陣的意義？(F1, F2)(F2,