動態(tài)規(guī)劃及其應用(二)(with pics)

1、動態(tài)規(guī)劃及其應用（二） 清華大學 楊志燦 動態(tài)規(guī)劃術(shù)語 階段 把所求解問題的過程恰當?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便于 求解 狀態(tài) 狀態(tài)表示每個階段開始面臨的自然狀況或客觀條件 決策（轉(zhuǎn)移） 一個階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個狀態(tài)的 一種選擇（行動）稱為決策。 邊界 轉(zhuǎn)移過程中的初始情況 策略 由每個階段的決策組成的序列稱為策略。對于每一個實際的多階 段決策過程，可選取的策略有一定的范圍限制，這個范圍稱為允 許策略集合。允許策略集合中達到最優(yōu)效果的策略稱為最優(yōu)策略。 動態(tài)規(guī)劃 Dynamic Programming 求解決策過程最優(yōu)化的數(shù)學方法 適用條件 最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)

2、性質(zhì)） 無后效性 子問題的重疊性 范圍 因同樣有狀態(tài)、轉(zhuǎn)移方程、無后效性等性質(zhì)，故將遞推等 類型也納入DP之下 如計算方案數(shù)、期望值 知道我要 說什么吧 攔截導彈 第一問 求LIS（最長上升子序列） 第二問 數(shù)列最少能拆成幾個上升子序列 NOIP 1999 senior p1 攔截導彈 求LIS（最長上升子序列） 普通DP：O（n2） 二分/數(shù)據(jù)結(jié)構(gòu)+DP：O（nlogn） 數(shù)列最少能拆成幾個上升子序列 貪心 每次用“最經(jīng)濟”的系統(tǒng)去打?qū)?模擬：O（n2） 數(shù)據(jù)結(jié)構(gòu)：O（nlogn） 合唱隊形 N位同學站成一排，音樂老師要請其中的(N-K)位同學 出列，使得剩下的K位同學排成合唱隊形。 合唱

3、隊形 設K位同學從左到右依次編號為1，2，K，他們的身高 分別為T1，T2，TK。 則他們的身高滿足T1.Ti+1TK(1=i=K)。 已知所有N位同學的身高，最少需要幾位同學出列， 可以使得剩下的同學排成合唱隊形。 2 = n = 100， 130 = Ti = 230 NOIP 2004 senior p2 合唱隊形 一個上升序列接一個下降序列？ 枚舉最高點 兩端DP fi為1, i中以第i個人作為終點的最長上升子序列 gi為i, n中以第i個人作為起點的最長下降子序列 ans = max fi + gi - 1； i1, n 時間復雜度 普通DP：O（n2） 二分/數(shù)據(jù)結(jié)構(gòu)+DP：O（n

4、logn） 金明的預算方案 n元錢買物品。物品分為主件和附件兩種，每個主件 可以有0個、1個或2個附件，附件不會再有附件。購 買附件必須先購買對應的主件。 每件物品有價值和重要度，最大化購買物品的重要度 之和 n = 3200， 物品個數(shù)m g21，且g2 g2 +1； 條件B：對于所有的i，g2g21，且g2 g2 +1。 請問，棟棟最多能將多少株花留在原地 1 = n = 100,000, 0 = hi hj) fi0 = max(fi0, fj1 + 1); else fi1 = max(fi1, fj0 + 1); O（n2） 用線段樹/樹狀數(shù)組加速轉(zhuǎn)移 O（nlogn） 計算拐點個數(shù)

5、 O（n） 烏龜棋 烏龜棋的棋盤是一行N個格子，每個格子上一個分數(shù)（非 負整數(shù)）。棋盤第1格是唯一的起點，第N格是終點。 烏龜棋有M張爬行卡片，分成4種不同的類型。 每種類型的卡片上分別標有1、2、3、4四個數(shù)字之一，表示使 用這種卡片后，烏龜棋子將向前爬行相應的格子數(shù)。 游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒有使 用過的爬行卡片，控制烏龜棋子前進相應的格子數(shù)。 游戲中，烏龜棋子自動獲得起點格子的分數(shù)，并且在后續(xù) 的爬行中每到達一個格子，就得到該格子相應的分數(shù)。 求小明最多能得到多少分 N = 350， M = 120 NOIP2010 senior p2 烏龜棋 Fni1i2i

6、3i4？ 狀態(tài)數(shù)：O（n*304） Fni1i2i3？ 第四種卡片使用數(shù)量可以通過格子數(shù)和另外三種卡片使用 數(shù)量計算得出 狀態(tài)數(shù)：O（n*303） Fi1i2i3i4 格子數(shù)可以通過已使用的四種卡片數(shù)量計算得出 狀態(tài)數(shù)：O（304） 時間復雜度 O（狀態(tài)數(shù)） 休息時間 傳紙條 n*m格子有權(quán)網(wǎng)格，從左上角（1, 1）到右下角（n, m）傳兩次紙條。 紙條只能向右或向下傳 一個格子只能經(jīng)過一次 兩傳紙條路徑除起點、終點外無交 最大化路徑和 n,m = 50 NOIP2008 senior p3 傳紙條 雙進程動態(tài)規(guī)劃 僅一條路徑 fij 兩條路徑 fiji2j2？ 保證兩路徑無交： （i, j）

7、和（i2, j2）必須在同一階段（斜線） 有廢狀態(tài) fxij 兩點分別位于第x斜線第i和第j位置 無廢狀態(tài) 時間復雜度 O（n3） 矩陣取數(shù)游戲 對于一個給定的n*m的矩陣，矩陣中的每個元素aij均為非 負整數(shù)。 1.每次取數(shù)時須從每行各取走一個元素，共n個。m次后 取完矩陣所有元素； 2.每次取走的各個元素只能是該元素所在行的行首或行 尾； 3.每次取數(shù)都有一個得分值，為每行取數(shù)的得分之和，每 行取數(shù)的得分=被取走的元素值*2i，其中i表示第i次取 數(shù)（從1開始編號）； 4.游戲結(jié)束總得分為m次取數(shù)得分之和。 求出給定矩陣的最大得分。 n, m = 80， 0 = aij = 1000 NO

8、IP2007 senior p3 矩陣取數(shù)游戲 行與行之間獨立 相當于n組數(shù)據(jù) 轉(zhuǎn)化為一維問題 兩端取數(shù) 任何時候剩余的數(shù)都構(gòu)成一個區(qū)間 區(qū)間DP fij表示區(qū)間i, j的最優(yōu)解 兩種解法 fij = max(ai + 2 * fi+1j, aj + 2 * fij-1); fij = max(ai*2(m-j+i) + fi+1j, aj*2(m-j+i) + fij-1) 上面兩種解法的狀態(tài)分別表示什么？ 時間復雜度：O（n*m2） 過河 青蛙想沿著獨木橋從河的一側(cè)跳到另一側(cè)。 由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可 以把獨木橋上青蛙可能到達的點看成數(shù)軸上的一串整點： 0，1，

9、L（其中L是橋的長度）。坐標為0的點表示 橋的起點，坐標為L的點表示橋的終點。 青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍 的距離是S到T之間的任意正整數(shù)（包括S,T）。當青蛙跳 到或跳過坐標為L的點時，就算青蛙已經(jīng)跳出了獨木橋。 給出橋上m個石子的位置。你的任務是確定青蛙要想過河， 最少需要踩到的石子數(shù)。 L = 109，1=S=T=10，1=m=100 NOIP 2005 senior p2 過河 fi表示跳到位置i至少要踩的石子數(shù) fi = min fi - x + stonei; xS, T ans = min fj; jL, L+T-1 O（L*(t s + 1)） L =

10、109，m = 100？ 離散化 若兩個相鄰石子之間的距離大于T，則可以將兩者之間的距 離縮短T 為什么不影響答案？ L = O（m * t） 時間復雜度 O（m * t2） 能量項鏈 火星人的能量項鏈上有n顆能量珠，能量珠是一顆有 頭標記與尾標記的珠子，標記均為正整數(shù) n顆珠子串成一個環(huán)，且前一顆珠子的尾標記等于后 一顆珠子的頭標記 相鄰兩顆珠子能聚合成一顆珠子，釋放出m*r*n單位 的能量 前一顆珠子頭標記為m，尾標記為r 后一顆珠子頭標記為r，尾標記為n 聚合后的珠子頭標記為m，尾標記為n 給定一個項鏈，求最大能釋放多少能量 n = 100 NOIP 2006 senior p1 能量項

11、鏈 區(qū)間DP 先考慮鏈上的問題 fij表示區(qū)間i, j的珠子能釋放出的最大能量值 區(qū)間i,j無論如何操作，最后聚合出的珠子的標記是固定的 枚舉決策分界點k，區(qū)間i,k和區(qū)間k+1,j分別聚合成一顆 珠子后，兩者再聚合 環(huán)上問題 破環(huán)成鏈 等長復制一遍 DP一遍后取最值 相當于枚舉斷點 時間復雜度 O（n3） 2k進制數(shù) 設r是個2k進制數(shù)，并滿足以下條件： r至少是個2位的2k進制數(shù)。 作為2k進制數(shù)，除最后一位外，r的每一位嚴格小于它右 邊相鄰的那一位。 將r轉(zhuǎn)換為2進制數(shù)q后，則q的總位數(shù)不超過w。 在這里，正整數(shù)k（1k9）和w（kw 30000） 是事先給定的。 滿足上述條件的不同的r

12、共有多少個？ NOIP 2006 senior p4 2k進制數(shù) 將r轉(zhuǎn)換為2進制數(shù)q后，則q的總位數(shù)不超過w。 r的位數(shù)最多為w/k (上整除） k不整除w時，r的首位不超過2(w%k) 1 除最后一位外，r的每一位嚴格小于它右邊相鄰的那一 位。 fij表示長度為i且最低位不超過j的數(shù)的個數(shù) 遞推方程 fij = fij-1 + fi-1j-1 答案統(tǒng)計 fi2k - 1，i1, w/k （下取整） 枚舉最高位x， fw/k2k 1 - x 高精度 加分二叉樹 一棵有點權(quán)的二叉樹 任一棵子樹subtree（也包含tree本身）的加分計算方 法如下：subtree的左子樹的加分subtree的右子樹 的加分subtree的根的分數(shù) 葉子的加分就是葉節(jié)點本身的權(quán)值 給定一棵n節(jié)點的二叉樹的中序遍歷和每個點的權(quán)值 求該樹的最高加分以及其前序遍歷 NOIP 2003 senior p3 加分二叉樹 中序遍歷？ 若ai為根