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

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

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

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

4、logn） 金明的預(yù)算方案 n元錢買物品。物品分為主件和附件兩種，每個(gè)主件 可以有0個(gè)、1個(gè)或2個(gè)附件，附件不會(huì)再有附件。購(gòu) 買附件必須先購(gòu)買對(duì)應(yīng)的主件。 每件物品有價(jià)值和重要度，最大化購(gòu)買物品的重要度 之和 n = 3200， 物品個(gè)數(shù)m g21，且g2 g2 +1； 條件B：對(duì)于所有的i，g2g21，且g2 g2 +1。 請(qǐng)問，棟棟最多能將多少株花留在原地 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） 計(jì)算拐點(diǎn)個(gè)數(shù)

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

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

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

8、IP2007 senior p3 矩陣取數(shù)游戲 行與行之間獨(dú)立 相當(dāng)于n組數(shù)據(jù) 轉(zhuǎn)化為一維問題 兩端取數(shù) 任何時(shí)候剩余的數(shù)都構(gòu)成一個(gè)區(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)分別表示什么？ 時(shí)間復(fù)雜度：O（n*m2） 過河 青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。 由于橋的長(zhǎng)度和青蛙一次跳過的距離都是正整數(shù)，我們可 以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)： 0，1，

9、L（其中L是橋的長(zhǎng)度）。坐標(biāo)為0的點(diǎn)表示 橋的起點(diǎn)，坐標(biāo)為L(zhǎng)的點(diǎn)表示橋的終點(diǎn)。 青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。一次跳躍 的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳 到或跳過坐標(biāo)為L(zhǎng)的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。 給出橋上m個(gè)石子的位置。你的任務(wù)是確定青蛙要想過河， 最少需要踩到的石子數(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？ 離散化 若兩個(gè)相鄰石子之間的距離大于T，則可以將兩者之間的距 離縮短T 為什么不影響答案？ L = O（m * t） 時(shí)間復(fù)雜度 O（m * t2） 能量項(xiàng)鏈 火星人的能量項(xiàng)鏈上有n顆能量珠，能量珠是一顆有 頭標(biāo)記與尾標(biāo)記的珠子，標(biāo)記均為正整數(shù) n顆珠子串成一個(gè)環(huán)，且前一顆珠子的尾標(biāo)記等于后 一顆珠子的頭標(biāo)記 相鄰兩顆珠子能聚合成一顆珠子，釋放出m*r*n單位 的能量 前一顆珠子頭標(biāo)記為m，尾標(biāo)記為r 后一顆珠子頭標(biāo)記為r，尾標(biāo)記為n 聚合后的珠子頭標(biāo)記為m，尾標(biāo)記為n 給定一個(gè)項(xiàng)鏈，求最大能釋放多少能量 n = 100 NOIP 2006 senior p1 能量項(xiàng)

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

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