為什么80%的碼農都做不了架構師？>>> ??

?

動態規劃 動態規劃
容易：
1018 , 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 ,
不易：
1019 , 1037 , 1080 , 1112 , 1141 , 1170 , 1192 , 1239 , 1655 , 1695 , 1707 , 1733 , 1737 , 1837 , 1850 , 1920 , 1934 , 1937 , 1964 , 2039 , 2138 , 2151 , 2161 , 2178 ,
推薦：
1015 , 1635 , 1636 , 1671 , 1682 , 1692 , 1704 , 1717 , 1722 , 1726 , 1732 , 1770 , 1821 , 1853 , 1949 , 2019 , 2127 , 2176 , 2228 , 2287 , 2342 , 2374 , 2378 , 2384 , 2411

1015 Jury Compromise
1029 False coin
1036 Gangsters
1037 A decorative fence
1038 Bugs Integrated, Inc.
1042 Gone Fishing
1050 To the Max
1062 昂貴的聘禮
1074 Parallel Expectations
1080 Human Gene Functions
1088 滑雪
1093 Formatting Text
1112 Team Them Up !
1141 Brackets Sequence
1143 Number Game
1157 LITTLE SHOP OF FLOWERS
1159 Palindrome
1160 Post Office
1163 The Triangle
1170 Shopping Offers
1178 Camelot
1179 Polygon
1180 Batch Scheduling
1185 炮兵陣地
1187 隕石的秘密
1189 釘子和小球
1191 棋盤分割
1192 最優連通子集
1208 The Blocks Problem
1239 Increasing Sequences
1240 Pre - Post - erous !
1276 Cash Machine
1293 Duty Free Shop
1322 Chocolate
1323 Game Prediction
1338 Ugly Numbers
1390 Blocks
1414 Life Line
1432 Decoding Morse Sequences
1456 Supermarket
1458 Common Subsequence
1475 Pushing Boxes
1485 Fast Food
1505 Copying Books
1513 Scheduling Lectures
1579 Function Run Fun
1609 Tiling Up Blocks
1631 Bridging signals 2分 + DP NLOGN
1633 Gladiators
1635 Subway tree systems
1636 Prison rearrangement
1644 To Bet or Not To Bet
1649 Market Place
1651 Multiplication Puzzle
1655 Balancing Act
1661 Help Jimmy
1664 放蘋果
1671 Rhyme Schemes
1682 Clans on the Three Gorges
1690 (Your)((Term)((Project)))
1691 Painting A Board
1692 Crossed Matchings
1695 Magazine Delivery
1699 Best Sequence
1704 Georgia and Bob
1707 Sum of powers
1712 Flying Stars
1714 The Cave
1717 Dominoes
1718 River Crossing
1722 SUBTRACT
1726 Tango Tango Insurrection
1732 Phone numbers
1733 Parity game
1737 Connected Graph
1740 A New Stone Game
1742 Coins P
1745 Divisibility
1770 Special Experiment
1771 Elevator Stopping Plan
1776 Task Sequences
1821 Fence
1837 Balance
1848 Tree
1850 Code
1853 Cat
1874 Trade on Verweggistan
1887 Testing the CATCHER
1889 Package Pricing
1920 Towers of Hanoi
1926 Pollution
1934 Trip
1936 All in All
1937 Balanced Food
1946 Cow Cycling
1947 Rebuilding Roads
1949 Chores
1952 BUY LOW, BUY LOWER
1953 World Cup Noise
1958 Strange Towers of Hanoi
1959 Darts
1962 Corporative Network
1964 City Game
1975 Median Weight Bead
1989 The Cow Lineup
2018 Best Cow Fences
2019 Cornfields
2029 Get Many Persimmon Trees
2033 Alphacode
2039 To and Fro
2047 Concert Hall Scheduling
2063 Investment
2081 Recaman ' s Sequence
2082 Terrible Sets
2084 Game of Connections
2127 Greatest Common Increasing Subsequence
2138 Travel Games
2151 Check the difficulty of problems
2152 Fire
2161 Chandelier
2176 Folding
2178 Heroes Of Might And Magic
2181 Jumping Cows
2184 Cow Exhibition
2192 Zipper
2193 Lenny ' s Lucky Lotto Lists
2228 Naptime
2231 Moo Volume
2279 Mr. Young ' s Picture Permutations
2287 Tian Ji -- The Horse Racing
2288 Islands and Bridges
2292 Optimal Keypad
2329 Nearest number - 2
2336 Ferry Loading II
2342 Anniversary party
2346 Lucky tickets
2353 Ministry
2355 Railway tickets
2356 Find a multiple
2374 Fence Obstacle Course
2378 Tree Cutting
2384 Harder Sokoban Problem
2385 Apple Catching
2386 Lake Counting
2392 Space Elevator
2397 Spiderman
2411 Mondriaan ' s Dream
2414 Phylogenetic Trees Inherited
2424 Flo ' s Restaurant
2430 Lazy Cows
2915 Zuma
3017 Cut the Sequence
3028 Shoot - out
3124 The Bookcase
3133 Manhattan Wiring
3345 Bribing FIPA
3375 Network Connection
3420 Quad Tiling

動態規劃總結

1 . 按狀態類型分
寫在前面：

從狀態類型分，并不表示一題只從屬于一類。其實一類只是一種狀態的表示方法。可以好幾種方法組合成一個狀態，來解決問題。

1.1 . 編號（長度）動態規劃
共性總結

本類的狀態是基礎的基礎，大部分的動態規劃都要用到它，成為一個維。

一般來說，有兩種編號的狀態：

狀態(i)表示前i個元素決策組成的一個狀態。

狀態(i)表示用到了第i個元素，和其他在1到i - 1間的元素，決策組成有的一個狀態。

題庫

a) 最長不下降子序列

以一元組(i)作為狀態，表示第i個作為序列的最后一個點的時候的最長序列。于是很容易想到O(n2)得算法。但本題可合理組織狀態，引入一個單調的輔助數組，利用單調性二分查找，優化到O(nlogn)。關于優化詳見優化章。

一些問題可將數據有序化，轉化成本題。

應用：

攔截導彈(NOIP99 Advance 1 ) 就是原題。

Beautiful People (sgu199)，要將數據有序化：其中一個權作為第一關鍵字不下降排列，另一個權作為第二關鍵字不上升。

Segment (ural 107 ，將線段的左端點有序化就可以了。

b) LCS

狀態(i,j)，表示第1個字符串的第i位，與第2個字符串的第j位匹配，得到的最長的串。若有多個串要LCS，則加維，即幾個串就幾個維。我也將此題歸入路徑問題。

c) 花店櫥窗布置(IOI99)

見路徑問題。

1.2 . 區間動態規劃
共性總結

本類問題與下一章的劃分問題的決策的分割點無序交集比較大（占本類問題的30 % ）。

題庫

a) 石子合并

見劃分問題

b) 模版匹配(CEOI01,Patten)

這題特殊的地方是狀態的值是一個集合而不是一個數。

c) 不可分解的編碼(ACM World Final 2002 )

d) Electric Path(ural1143)

e) 郵局(IOI2000 Day2 1 )

若狀態表示的思路從第i個村莊可以從屬于哪個郵局，無最優子結構。轉變一個方向：第k個郵局可以“控制”一個區間的村莊[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]間最好的一個郵局點。

不過可以發現Sum{ | S(k) - S(p) | 是單調的，所以取中位數就可以了。即上式中k的取值范圍只有floor((i + j) / 2 ), ceil((i + j) / 2 )兩個。Floor是下取整。Ceil是上取整。這樣每次轉移時間降到O( 1 )。

注意到是區間連續的，即(p,i - 1 ) 和(i, j) 中的 i - 1 , i是連續的，所以空間可以降維：f(i,j)表示放前i個郵局到前j個村莊的最優值。

f(i,j) = min{f(i - 1 ,p - 1 ) + w(p,j)}(i - 1 <= p <= j - 1 }

e(i,j) 為當f(i,j)到達最優值時的p.

通過證明四邊形不等式，得到e(i,j) <= e(i,j + 1 ) <= e(i + 1 ,j + 1 )

決策數量又少了一個數量級。

1.3 . 坐標動態規劃
共性總結

之后的一些問題，狀態是由坐標維與其他的維組成。本類與劃分問題(是2維或多維的坐標系的劃分)與路徑問題的交集占本類問題中大多數。

題庫

a) 棋盤分割(NOI99 4 )

主要是將公式變形，變形后的公式很容易看出方程。

狀態是由2個坐標組成的4元組(x1,y1)(x2,y2)，表示一個子棋盤。這有點像之前的區間動態規劃，只不過是將1維轉2維。

后見路徑問題。

1.4 . 數軸動態規劃
共性總結

題庫

a) 01背包

應用：

裝箱問題（NOIP01 Trade 4 ）

就是原題。

值幣分割

可利用方程的性質，空間降1維。

幣值可重復的值幣分割(pku1742, Problem F LouTianCheng’s Contest in POJ)

使用左右法在定位上加速。

另給狀態加一個屬性last,記錄上一次剩下的可用的同幣值硬幣數（利用了當前轉移是唯一前驅的特點）。

b) 取火柴問題(sgu153 Playing with matches)

c) Stone Pile(ural1005 Stone Pile)

d) 公路巡邏(CTSC2000)

1.5 . 5 .樹型動態規劃
共性總結

1 ） 動態規劃的順序

一般按照后序遍歷的順序，即處理完兒子再處理當前節點，才符合樹的子結構的性質。

2 ） 多叉樹轉換為二叉樹

由于要分配附加維到各個節點，而分配附加維是個劃分問題，若還是按當前節點到各個兒子節點分配，則成了一個整數劃分問題,O(n- 2 )。所以要把多叉樹轉換為二叉樹，這樣才能按動態規劃的方式只決策當前點的分配問題, O(n-)。

3 ） 加當前點的選或不選的常數維

加此維解決的是后效性問題。

……………………

4 ） 在將邊信息轉成樹時的技巧

將讀入的邊分裂成2條邊，將這2條邊關聯起來（就是找到一條邊，另一條邊的編號就知道）。用前向星表示法表示邊（按起點有序），以后用邊的時候，用了一條 邊打不可用標志，也將關聯邊打不可用標志。這樣可以保證O(n)的時間完成信息處理，而且在父節點找兒子的過程中帶來很大的方便。

5 ） 復雜度

樹型動態規劃復雜度基本上是O(n)；若有附加維m，則是O(nm)。

題庫

a) 選課(CTSC97 - 3 )

由于要分配課程數，所以要多叉樹轉換為二叉樹。

b) 貪吃的九頭龍(NOI02 - 3 )

若小頭數大于1的話，則讓不同的小頭吃一段樹枝的2個端點。

這樣就把問題轉化成：附加維是大頭吃的個數，當前點由不由大頭吃的常數維的動態規劃。由于涉及劃分問題，所以要多叉樹轉換為二叉樹。

c) 求樹的質心(sgu134 Centroid)

給出一棵邊不帶權的樹，求點,使得去掉此點后,剩下的最大的連通子圖的頂點數最小.

d) 求樹中的點最遠距離最近。

給出一棵邊帶權的樹，求樹中的點，使得此點到樹中的其他結點的最遠距離最近。

Computer Network (sgu149)

Computer Net (ural1056)

1.6 . 集合動態規劃（狀態壓縮）
共性總結

1 ) 數據特殊性

給出的數據在某一個或幾個維度上一般具有比較小的范圍（可以枚舉一類的狀態）。

一個枚舉的狀態是一個集合。

2 ) 編碼

由于集合中元素個數的不定性或范圍大，直接開數組存，不好索引數組（編程復雜度太高），所以要將集合編碼。

利用數據的可枚舉性，將枚舉的狀態(集合)編碼。一般來說碼值的范圍要很小（盡量排除無用的碼值，如炮兵：當前格和上格存在炮兵的情況是非法的，可以排除）。

規定編碼的碼值代表的意思，要盡量規定好維護的碼值。（如炮兵：當前格存在炮兵的用2，上格存在炮兵用1。這樣下一層的規劃時，只要碼值 - 1即可）。

有時候可以直接利用編碼的順序動態規劃，因為這時編碼已經是拓補有序。如TSP問題當前已選點集合的狀態的前驅的編碼的值一定比當前的編碼的值小。

3 ) 狀態壓縮

對有限階段的放置情況，行走情況編碼（其實質也是放置的集合或行走路線的集合），這樣的編碼，也有人謂之：“狀態壓縮”。此類題以“炮兵陣地”為典型，進行擴展。

題庫

a) 購物（IOI95 - 2 ）

可將每種物品按5進制編碼。（5為每種物品數的上限）

由于物品數的上限為5，比較小，也可直接開數組存。

b) Roger游戲任務一（CTSC98 Day2 4 ）

一個正方體在一個方格內的狀態只有24種，而且可以通過頂面和前面來表示，這樣用3維的狀態(x,y,p)就可以解決，p為1到24種狀態中的一種。

c) TSP問題

觀察一下TSP的搜索過程： for (x in 未選點) TSP(x)

即當前路的最后一個節點為x,現在要選擇下一個節點y,而y要在未選點的集合中。若未選點或已選點的集合已確定，則后效性消除。可以DP。狀態為令X為當 前路的已選點的集合(含i)，當前路的最后一個節點為i。2元組(X,i)為經過已選點的集合X到節點i的最短長度。將X編碼即可。

注意：并沒有因為動態規劃將問題從NP類帶到P類。

應用: DNA Laboratory(Problem B,TU - Darmstadt Programming Contest 2004 )

將每個串的交迭部分求出，就可以將問題專成TSP

但要輸出字典序最小的，則需要注意DP順序。

有具體的報告。

d) 炮兵陣地

十分經典，詳見報告。

應用:

Another Chocolate Maniac(sgu132) 類似炮兵的做法的最值，只不過是求最小值，麻煩點。

Hardwood floor(sgu131) 類似炮兵的做法的統計

Little Knights(sgu225) 類似炮兵的做法的統計,數據量太大要const

Little Kings(sgu223) 類似炮兵的做法的統計

Bugs公司(CEOI 2002 ) 類似炮兵的做法的最值

1.7 . 利用動態規劃思想求最值，編號（循環變量）的迭代
共性總結

要利用上次的一些運算“剩下”的循環變量作當前循環的邊界，主要在于找出一種決策順序，使之成立。

題庫

a) 奶牛浴場

b) Communication System

將數據有序化, 從大到小枚舉帶寬, 每次可利用上次處理的結果Min, 來決策當前狀態。稱作迭代, 或就是一種動態規劃。

(zju1409, Problem C Tehran 2002 Iran Nationwide Internet Programming Contest)

1.8 . 記憶化搜索
題庫

a) Magic Trick (Problem G, TU - Darmstadt Programming Contest 2004 )

2 . 按轉移方式分
2.1 . 存在性
遞推

1 )01統計(CTSC99 1 )

2 )卡特蘭數

circle(sgu130)

3 )鷹蛋

2.2 . 求一系列的分割（合并）點（劃分問題）
2.2 . 1 . 決策的分割點有序
共性總結

a) 有序性

每次決策的點的編號是有序的，即要按決策的順序輸出分割點的編號的話，編號是有序的，滿足分割點的編號按升序排列。

b) 方程一般形式

f(n,m) = optimize{f(k,m - 1 ) + w(k + 1 ,n)}

(n,m)表示從1到n個點中劃分為m個部分的最優值；k為決策的分割點，即第m個部分為k + 1到n；這里optimize可以為max,min。

題庫

a) 整數劃分

常應用在將一個權分配給一定的小分割塊，如：將大堆的石子分成一定的小堆，小堆可為空，大堆要分完。有時應用在樹型動態規劃（二叉轉多叉）中。

b) 乘積最大(NOIP00 Advance 2 )

就是按上面的一般式的方程做。

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的最優值，子問題是分割點左邊(i,k - 1 )和右邊(k + 1 ,j)的點的范圍的最優值；這里optimize可以為max,min。

方程很類似2叉樹的性質。

c) 四邊形不等式

此類的問題，有些可用四邊形不等式優化。見優化章。

題庫

a) 石子合并(NOI95 2 )

經典，詳見報告。

可用四邊形不等式優化成O(n2)

其實還可以用類似堆的數據結構在O(nlogn)的時間內完成，但這就不是動態規劃了。

應用：

構造最優二叉排序樹(CTSC96 2 )

b) 多邊形(IOI9

這題值的正負號處理要注意，乘法運算，由于符號的加入，使原本的正的最優解，一下變成負的。

c) 加分二叉樹(NOIP03 Advance 3 )

方程就是一般式，轉移的函數：w(i,j) = sum(i,k - 1 ) * sum(k + 1 ,j) + d(k)。由于w(i,j)不滿足凸單調性，所以不能用四邊形不等式優化。

d) 括號序列(Problem B, NEERC 2001 )

這題的分割點不是一個元素，而是元素間的一條線。

主要的思維方式是從遞歸定義。

2.3 . 路徑問題
共性總結

a) 行走方向決定階段性

有規定源點與終點。每次行走方向都有一定的規定，使原點到終點的所有路徑形成無環有向圖。

b) 多源或多匯

當多源或多匯時，應該加維，使得每個源，都有一個路徑的狀態與之對應。如有n個源的網格類問題，常常轉態是(x1,y1)(x2,y2)…(xn,yn)。但是源太多的話，空間上不允許，可以降問題轉成網絡流問題。

c) 雙向動態規劃

由于有規定源點與終點，可以雙向動態規劃，但要考慮效果好不好，理論上是比原來少1 / 2 ，但有時由于可用于決策的狀態較少，效果就不錯了。

d) 決策稀疏性

就是所謂走法，若對于一個狀態，它的前驅或者后繼數很少(從無環有向圖角度，就是入度或出度少)，稱決策稀疏。

e) 狀態稀疏性

就是很多狀態是沒有用的，如排列的LCS,狀態為2維的(x,y)，但對于一個x只有一個y是有效個。所以實質上狀態數還是線形的。

本類一些技巧性的東西較多，在題庫中具體說明。

題庫

a) 方格取數(NOIP00 advance 4 )

(x1,y1)(x2,y2)

對角線空間優化

b) 花店櫥窗布置(IOI99)

我對本題有個小改造：若花瓶無序，如何做，有序指：對于花束i < 花束j, 花束i對應的花瓶編號 < 花束j對應的花瓶編號。那么這樣就是一個NP問題了，可用后面的基于狀態壓縮的動態規劃解決。

3 . 動態規劃的優化
3.1 . 迭代
3.2 . 四邊形
3.3 . 凸性的優化

?

轉載于:https://my.oschina.net/garyun/blog/602868

總結

以上是生活随笔為你收集整理的【转】别人整理的DP大全的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。