别人整理的dp大全
動態(tài)規(guī)劃
動態(tài)規(guī)劃
容易：
, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926, 1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029, , 2063, 2081, 2082, 2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385, 2392, 2424,
不易：
, 1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707, 1733, 1737, 1837, 1850, 1920, 1934, 1937, 1964, 2039, 2138, 2151, 2161, 2178,
推薦：
, 1635, 1636, 1671, 1682, 1692, 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411
?Jury Compromise
?False coin
?Gangsters
?A decorative fence
?Bugs Integrated, Inc.
?Gone Fishing
?To the Max
?昂貴的聘禮
?Parallel Expectations
?Human Gene Functions
?滑雪
?Formatting Text
?Team Them Up!
?Brackets Sequence
?Number Game
?LITTLE SHOP OF FLOWERS
?Palindrome
?Post Office
?The Triangle
?Shopping Offers
?Camelot
?Polygon
?Batch Scheduling
?炮兵陣地
?隕石的秘密
?釘子和小球
?棋盤分割
?最優(yōu)連通子集
?The Blocks Problem
?Increasing Sequences
?Pre-Post-erous!
?Cash Machine
?Duty Free Shop
?Chocolate
?Game Prediction
?Ugly Numbers
?Blocks
?Life Line
?Decoding Morse Sequences
?Supermarket
?Common Subsequence
?Pushing Boxes
?Fast Food
?Copying Books
?Scheduling Lectures
?Function Run Fun
?Tiling Up Blocks
?Bridging signals 2分+DP NLOGN
?Gladiators
?Subway tree systems
?Prison rearrangement
?To Bet or Not To Bet
?Market Place
?Multiplication Puzzle
?Balancing Act
?Help Jimmy
?放蘋果
?Rhyme Schemes
?Clans on the Three Gorges
?(Your)((Term)((Project)))
?Painting A Board
?Crossed Matchings
?Magazine Delivery
?Best Sequence
?Georgia and Bob
?Sum of powers
?Flying Stars
?The Cave
?Dominoes
?River Crossing
?SUBTRACT
?Tango Tango Insurrection
?Phone numbers
?Parity game
?Connected Graph
?A New Stone Game
?Coins P
?Divisibility
?Special Experiment
?Elevator Stopping Plan
?Task Sequences
?Fence
?Balance
?Tree
?Code
?Cat
?Trade on Verweggistan
?Testing the CATCHER
?Package Pricing
?Towers of Hanoi
?Pollution
?Trip
?All in All
?Balanced Food
?Cow Cycling
?Rebuilding Roads
?Chores
?BUY LOW, BUY LOWER
?World Cup Noise
?Strange Towers of Hanoi
?Darts
?Corporative Network
?City Game
?Median Weight Bead
?The Cow Lineup
?Best Cow Fences
?Cornfields
?Get Many Persimmon Trees
?Alphacode
?To and Fro
?Concert Hall Scheduling
?Investment
?Recaman's Sequence
?Terrible Sets
?Game of Connections
?Greatest Common Increasing Subsequence
?Travel Games
?Check the difficulty of problems
?Fire
?Chandelier
?Folding
?Heroes Of Might And Magic
?Jumping Cows
?Cow Exhibition
?Zipper
?Lenny's Lucky Lotto Lists
?Naptime
?Moo Volume
?Mr. Young's Picture Permutations
?Tian Ji -- The Horse Racing
?Islands and Bridges
?Optimal Keypad
?Nearest number - 2
?Ferry Loading II
?Anniversary party
?Lucky tickets
?Ministry
?Railway tickets
?Find a multiple
?Fence Obstacle Course
?Tree Cutting
?Harder Sokoban Problem
?Apple Catching
?Lake Counting
?Space Elevator
?Spiderman
?Mondriaan's Dream
?Phylogenetic Trees Inherited
?Flo's Restaurant
?Lazy Cows
?Zuma
?Cut the Sequence
?Shoot-out
?The Bookcase
?Manhattan Wiring
?Bribing FIPA
?Network Connection
?Quad Tiling
動態(tài)規(guī)劃總結
. 按狀態(tài)類型分
寫在前面：
從狀態(tài)類型分，并不表示一題只從屬于一類。其實一類只是一種狀態(tài)的表示方法。可以好幾種方法組合成一個狀態(tài)，來解決問題。
.1. 編號（長度）動態(tài)規(guī)劃
共性總結
本類的狀態(tài)是基礎的基礎，大部分的動態(tài)規(guī)劃都要用到它，成為一個維。
一般來說，有兩種編號的狀態(tài)：
狀態(tài)(i)表示前i個元素決策組成的一個狀態(tài)。
狀態(tài)(i)表示用到了第i個元素，和其他在1到i-1間的元素，決策組成有的一個狀態(tài)。
題庫
a) 最長不下降子序列
以一元組(i)作為狀態(tài)，表示第i個作為序列的最后一個點的時候的最長序列。于是很容易想到O(n2)得算法。但本題可合理組織狀態(tài)，引入一個單調的輔助數(shù)組，利用單調性二分查找，優(yōu)化到O(nlogn)。關于優(yōu)化詳見優(yōu)化章。
一些問題可將數(shù)據(jù)有序化，轉化成本題。
應用：
攔截導彈(NOIP99 Advance 1) 就是原題。
Beautiful People (sgu199)，要將數(shù)據(jù)有序化：其中一個權作為第一關鍵字不下降排列，另一個權作為第二關鍵字不上升。
Segment (ural 107，將線段的左端點有序化就可以了。
b) LCS
狀態(tài)(i,j)，表示第1個字符串的第i位，與第2個字符串的第j位匹配，得到的最長的串。若有多個串要LCS，則加維，即幾個串就幾個維。我也將此題歸入路徑問題。
c) 花店櫥窗布置(IOI99)
見路徑問題。
.2. 區(qū)間動態(tài)規(guī)劃
共性總結
本類問題與下一章的劃分問題的決策的分割點無序交集比較大（占本類問題的30%）。
題庫
a) 石子合并
見劃分問題
b) 模版匹配(CEOI01,Patten)
這題特殊的地方是狀態(tài)的值是一個集合而不是一個數(shù)。
c) 不可分解的編碼(ACM World Final 2002)
d) Electric Path(ural1143)
e) 郵局(IOI2000 Day2 1)
若狀態(tài)表示的思路從第i個村莊可以從屬于哪個郵局，無最優(yōu)子結構。轉變一個方向：第k個郵局可以“控制”一個區(qū)間的村莊[i,j]。于是方程就顯然了:
f(k,i,j)=min{f(k-1,p,i-1)+w(i,j)}(k-1<=p<=i-1)
S(i) 為村莊i到原點的距離。
w(i,j)=min{k| Sum{|S(k)-S(p)|}(i<=p<=j)}(i<=k<=j) 找到[i,j]間最好的一個郵局點。
不過可以發(fā)現(xiàn)Sum{|S(k)-S(p)|是單調的，所以取中位數(shù)就可以了。即上式中k的取值范圍只有floor((i+j)/2), ceil((i+j)/2)兩個。Floor是下取整。Ceil是上取整。這樣每次轉移時間降到O(1)。
注意到是區(qū)間連續(xù)的，即(p,i-1) 和(i, j) 中的 i-1, i是連續(xù)的，所以空間可以降維：f(i,j)表示放前i個郵局到前j個村莊的最優(yōu)值。
f(i,j)=min{f(i-1,p-1)+w(p,j)}(i-1<=p<=j-1}
e(i,j) 為當f(i,j)到達最優(yōu)值時的p.
通過證明四邊形不等式，得到e(i,j)<=e(i,j+1)<=e(i+1,j+1)
決策數(shù)量又少了一個數(shù)量級。
.3. 坐標動態(tài)規(guī)劃
共性總結
之后的一些問題，狀態(tài)是由坐標維與其他的維組成。本類與劃分問題(是2維或多維的坐標系的劃分)與路徑問題的交集占本類問題中大多數(shù)。
題庫
a) 棋盤分割(NOI99 4)
主要是將公式變形，變形后的公式很容易看出方程。
狀態(tài)是由2個坐標組成的4元組(x1,y1)(x2,y2)，表示一個子棋盤。這有點像之前的區(qū)間動態(tài)規(guī)劃，只不過是將1維轉2維。
后見路徑問題。
.4. 數(shù)軸動態(tài)規(guī)劃
共性總結
題庫
a) 01背包
應用：
裝箱問題（NOIP01 Trade 4）
就是原題。
值幣分割
可利用方程的性質，空間降1維。
幣值可重復的值幣分割(pku1742, Problem F LouTianCheng’s Contest in POJ)
使用左右法在定位上加速。
另給狀態(tài)加一個屬性last,記錄上一次剩下的可用的同幣值硬幣數(shù)（利用了當前轉移是唯一前驅的特點）。
b) 取火柴問題(sgu153 Playing with matches)
c) Stone Pile(ural1005 Stone Pile)
d) 公路巡邏(CTSC2000)
.5. 5.樹型動態(tài)規(guī)劃
共性總結
） 動態(tài)規(guī)劃的順序
一般按照后序遍歷的順序，即處理完兒子再處理當前節(jié)點，才符合樹的子結構的性質。
） 多叉樹轉換為二叉樹
由于要分配附加維到各個節(jié)點，而分配附加維是個劃分問題，若還是按當前節(jié)點到各個兒子節(jié)點分配，則成了一個整數(shù)劃分問題,O(n-2)。所以要把多叉樹轉換為二叉樹，這樣才能按動態(tài)規(guī)劃的方式只決策當前點的分配問題, O(n-)。
） 加當前點的選或不選的常數(shù)維
加此維解決的是后效性問題。
……………………
） 在將邊信息轉成樹時的技巧
將讀入的邊分裂成2條邊，將這2條邊關聯(lián)起來（就是找到一條邊，另一條邊的編號就知道）。用前向星表示法表示邊（按起點有序），以后用邊的時候，用了一條 邊打不可用標志，也將關聯(lián)邊打不可用標志。這樣可以保證O(n)的時間完成信息處理，而且在父節(jié)點找兒子的過程中帶來很大的方便。
） 復雜度
樹型動態(tài)規(guī)劃復雜度基本上是O(n)；若有附加維m，則是O(nm)。
題庫
a) 選課(CTSC97-3)
由于要分配課程數(shù)，所以要多叉樹轉換為二叉樹。
b) 貪吃的九頭龍(NOI02-3)
若小頭數(shù)大于1的話，則讓不同的小頭吃一段樹枝的2個端點。
這樣就把問題轉化成：附加維是大頭吃的個數(shù)，當前點由不由大頭吃的常數(shù)維的動態(tài)規(guī)劃。由于涉及劃分問題，所以要多叉樹轉換為二叉樹。
c) 求樹的質心(sgu134 Centroid)
給出一棵邊不帶權的樹，求點,使得去掉此點后,剩下的最大的連通子圖的頂點數(shù)最小.
d) 求樹中的點最遠距離最近。
給出一棵邊帶權的樹，求樹中的點，使得此點到樹中的其他結點的最遠距離最近。
Computer Network (sgu149)
Computer Net (ural1056)
.6. 集合動態(tài)規(guī)劃（狀態(tài)壓縮）
共性總結
) 數(shù)據(jù)特殊性
給出的數(shù)據(jù)在某一個或幾個維度上一般具有比較小的范圍（可以枚舉一類的狀態(tài)）。
一個枚舉的狀態(tài)是一個集合。
) 編碼
由于集合中元素個數(shù)的不定性或范圍大，直接開數(shù)組存，不好索引數(shù)組（編程復雜度太高），所以要將集合編碼。
利用數(shù)據(jù)的可枚舉性，將枚舉的狀態(tài)(集合)編碼。一般來說碼值的范圍要很小（盡量排除無用的碼值，如炮兵：當前格和上格存在炮兵的情況是非法的，可以排除）。
規(guī)定編碼的碼值代表的意思，要盡量規(guī)定好維護的碼值。（如炮兵：當前格存在炮兵的用2，上格存在炮兵用1。這樣下一層的規(guī)劃時，只要碼值-1即可）。
有時候可以直接利用編碼的順序動態(tài)規(guī)劃，因為這時編碼已經是拓補有序。如TSP問題當前已選點集合的狀態(tài)的前驅的編碼的值一定比當前的編碼的值小。
) 狀態(tài)壓縮
對有限階段的放置情況，行走情況編碼（其實質也是放置的集合或行走路線的集合），這樣的編碼，也有人謂之：“狀態(tài)壓縮”。此類題以“炮兵陣地”為典型，進行擴展。
題庫
a) 購物（IOI95-2）
可將每種物品按5進制編碼。（5為每種物品數(shù)的上限）
由于物品數(shù)的上限為5，比較小，也可直接開數(shù)組存。
b) Roger游戲任務一（CTSC98 Day2 4）
一個正方體在一個方格內的狀態(tài)只有24種，而且可以通過頂面和前面來表示，這樣用3維的狀態(tài)(x,y,p)就可以解決，p為1到24種狀態(tài)中的一種。
c) TSP問題
觀察一下TSP的搜索過程： for (x in 未選點) TSP(x)
即當前路的最后一個節(jié)點為x,現(xiàn)在要選擇下一個節(jié)點y,而y要在未選點的集合中。若未選點或已選點的集合已確定，則后效性消除。可以DP。狀態(tài)為令X為當 前路的已選點的集合(含i)，當前路的最后一個節(jié)點為i。2元組(X,i)為經過已選點的集合X到節(jié)點i的最短長度。將X編碼即可。
注意：并沒有因為動態(tài)規(guī)劃將問題從NP類帶到P類。
應用: DNA Laboratory(Problem B,TU-Darmstadt Programming Contest 2004)
將每個串的交迭部分求出，就可以將問題專成TSP
但要輸出字典序最小的，則需要注意DP順序。
有具體的報告。
d) 炮兵陣地
十分經典，詳見報告。
應用:
Another Chocolate Maniac(sgu132) 類似炮兵的做法的最值，只不過是求最小值，麻煩點。
Hardwood floor(sgu131) 類似炮兵的做法的統(tǒng)計
Little Knights(sgu225) 類似炮兵的做法的統(tǒng)計,數(shù)據(jù)量太大要const
Little Kings(sgu223) 類似炮兵的做法的統(tǒng)計
Bugs公司(CEOI 2002) 類似炮兵的做法的最值
.7. 利用動態(tài)規(guī)劃思想求最值，編號（循環(huán)變量）的迭代
共性總結
要利用上次的一些運算“剩下”的循環(huán)變量作當前循環(huán)的邊界，主要在于找出一種決策順序，使之成立。
題庫
a) 奶牛浴場
b) Communication System
將數(shù)據(jù)有序化, 從大到小枚舉帶寬, 每次可利用上次處理的結果Min, 來決策當前狀態(tài)。稱作迭代, 或就是一種動態(tài)規(guī)劃。
(zju1409, Problem C Tehran 2002 Iran Nationwide Internet Programming Contest)
.8. 記憶化搜索
題庫
a) Magic Trick (Problem G, TU-Darmstadt Programming Contest 2004)
. 按轉移方式分
.1. 存在性
遞推
)01統(tǒng)計(CTSC99 1)
)卡特蘭數(shù)
circle(sgu130)
)鷹蛋
.2. 求一系列的分割（合并）點（劃分問題）
.2.1. 決策的分割點有序
共性總結
a) 有序性
每次決策的點的編號是有序的，即要按決策的順序輸出分割點的編號的話，編號是有序的，滿足分割點的編號按升序排列。
b) 方程一般形式
f(n,m)=optimize{f(k,m-1)+w(k+1,n)}
(n,m)表示從1到n個點中劃分為m個部分的最優(yōu)值；k為決策的分割點，即第m個部分為k+1到n；這里optimize可以為max,min。
題庫
a) 整數(shù)劃分
常應用在將一個權分配給一定的小分割塊，如：將大堆的石子分成一定的小堆，小堆可為空，大堆要分完。有時應用在樹型動態(tài)規(guī)劃（二叉轉多叉）中。
b) 乘積最大(NOIP00 Advance 2)
就是按上面的一般式的方程做。
.2.2. 決策的分割點無序
共性總結
a) 無序性
每次決策的點的編號是無序的，即要按決策的遞歸順序輸出分割點的編號的話，編號是無序的。
b) 方程一般形式
f(i,j)=optimize{f(i,k-1)+f(k+1,j)}+w(i,j)
(i,j)表示從i到j的范圍內選取一個分割點k的最優(yōu)值，子問題是分割點左邊(i,k-1)和右邊(k+1,j)的點的范圍的最優(yōu)值；這里optimize可以為max,min。
方程很類似2叉樹的性質。
c) 四邊形不等式
此類的問題，有些可用四邊形不等式優(yōu)化。見優(yōu)化章。
題庫
a) 石子合并(NOI95 2)
經典，詳見報告。
可用四邊形不等式優(yōu)化成O(n2)
其實還可以用類似堆的數(shù)據(jù)結構在O(nlogn)的時間內完成，但這就不是動態(tài)規(guī)劃了。
應用：
構造最優(yōu)二叉排序樹(CTSC96 2)
b) 多邊形(IOI9
這題值的正負號處理要注意，乘法運算，由于符號的加入，使原本的正的最優(yōu)解，一下變成負的。
c) 加分二叉樹(NOIP03 Advance 3)
方程就是一般式，轉移的函數(shù)：w(i,j)=sum(i,k-1)*sum(k+1,j)+d(k)。由于w(i,j)不滿足凸單調性，所以不能用四邊形不等式優(yōu)化。
d) 括號序列(Problem B, NEERC 2001)
這題的分割點不是一個元素，而是元素間的一條線。
主要的思維方式是從遞歸定義。
.3. 路徑問題
共性總結
a) 行走方向決定階段性
有規(guī)定源點與終點。每次行走方向都有一定的規(guī)定，使原點到終點的所有路徑形成無環(huán)有向圖。
b) 多源或多匯
當多源或多匯時，應該加維，使得每個源，都有一個路徑的狀態(tài)與之對應。如有n個源的網(wǎng)格類問題，常常轉態(tài)是(x1,y1)(x2,y2)…(xn,yn)。但是源太多的話，空間上不允許，可以降問題轉成網(wǎng)絡流問題。
c) 雙向動態(tài)規(guī)劃
由于有規(guī)定源點與終點，可以雙向動態(tài)規(guī)劃，但要考慮效果好不好，理論上是比原來少1/2，但有時由于可用于決策的狀態(tài)較少，效果就不錯了。
d) 決策稀疏性
就是所謂走法，若對于一個狀態(tài)，它的前驅或者后繼數(shù)很少(從無環(huán)有向圖角度，就是入度或出度少)，稱決策稀疏。
e) 狀態(tài)稀疏性
就是很多狀態(tài)是沒有用的，如排列的LCS,狀態(tài)為2維的(x,y)，但對于一個x只有一個y是有效個。所以實質上狀態(tài)數(shù)還是線形的。
本類一些技巧性的東西較多，在題庫中具體說明。
題庫
a) 方格取數(shù)(NOIP00 advance 4)
(x1,y1)(x2,y2)
對角線空間優(yōu)化
b) 花店櫥窗布置(IOI99)
我對本題有個小改造：若花瓶無序，如何做，有序指：對于花束i<花束j, 花束i對應的花瓶編號<花束j對應的花瓶編號。那么這樣就是一個NP問題了，可用后面的基于狀態(tài)壓縮的動態(tài)規(guī)劃解決。
. 動態(tài)規(guī)劃的優(yōu)化
.1. 迭代
.2. 四邊形
.3. 凸性的優(yōu)化
總結
- 上一篇： 分组背包基础--1712 ACboy n
- 下一篇： 记忆化搜素，和递推法