信息學競賽寶典 動態規劃

張新華

中學高級教師，信息學競賽教練。取得浙江大學計算機科學與技術學士學位、廈門大學軟件工程碩士學位，獲得2009年普通高中信息技術現場優質課比賽全國一等獎。培養的學生多次獲得全國青少年奧林匹克聯賽國家一等獎及亞太與太平洋地區信息學奧林匹克競賽獎牌。著有“信息學競賽寶典”系列書。開發了三維圖形化C++編程工具Dev-C++智能開發平台和Python可視化界面設計軟件Visual Python。

胡向榮

安徽省信息學競賽金牌教練。獲得中國首屆網絡管理員大賽亞軍，安徽省首屆計算機技術大賽一等獎，安徽省信息技術優質課評選一等獎。安慶市教育技術專家、信息技術學科骨幹教師、先進教研個人。

伍婉秋

初中信息技術一級教師，廣州市白雲區永平片初二信息技術教研組組長；參與教育部全國教育科學“十三五”規劃課題“三維圖形化智能編程系統在中小學編程教育中的構建和應用”；曾獲廣州市中學信息技術教師教學能力比賽二等獎、白雲區一等獎。

目錄

CONTENTS

 

第 1章　最長不下降子序列問題

1.1.最長不下降子序列　/　1

1.2.抄近路　/　6

1.3.寶藏　/　7

1.4.導彈攔截　/　8

1.5.和諧俱樂部　/　9

1.6.滑雪　/　10

1.7.拓展與練習　/　12

 

第 2章 背包問題

2.1.簡單背包問題　/　13

2.2.0/1背包問題　/　15

2.3.0/1背包算法的優化　/　17

2.4.分組背包問題　/　18

2.4.1.二維數組動態規劃算法　/　19

2.4.2.一維數組優化算法　/　20

2.5.拓展與練習　/　21

 

第3章 完全背包問題

3.1.完全背包　/　22

3.2.完全背包算法的優化　/　23

3.3.拓展與練習 　/　24

 

第4章 多重背包問題

4.1.多重背包　/　25

4.2.通天塔　/　27

4.3.忙碌　/　28

4.4.拓展與練習　/　29

 

第5章 二維費用背包問題

5.1.訓練賽　/　30

5.2.電腦游戲　/　31

5.3.拓展與練習　/　32

 

第6章 區間動態規劃

6.1.書架問題1　/　33

6.2.書架問題2　/　35

6.3.收購珍珠　/　37

6.4.雙色馬　/　38

6.5.歸並石子１　/　39

6.6.切割銅棒　/　44

6.7.郵局問題　/　45

6.8.乘積最大　/　47

6.9.凸多邊形三角劃分　/　49

6.10.凸多邊形分割　/　51

6.11.拓展與練習　/　54

 

第7章 路徑問題

7.1.最短路徑　/　55

7.2.最少交通費用問題　/　60

7.3.拓展與練習　/　62

 

第8章 資源類動態規劃

8.1.機器分配　/　63

8.2.調度問題　/　64

8.3.系統可靠性　/　66

8.4.購物　/　67

8.5.快餐問題　/　69

8.6.拓展與練習　/　71

 

第9章 動態規劃的簡單優化

9.1.絲綢之路　/　72

9.1.1.動態規劃算法一　/　73

9.1.2.動態規劃算法二　/　73

9.1.3.動態規劃算法三　/　74

9.2.雙人游戲　/　75

9.2.1.動態規劃算法一　/　76

9.2.2.動態規劃算法二　/　76

9.3.理想收入問題　/　77

9.3.1.樸素算法　/　78

9.3.2.優化算法一　/　78

9.3.3.優化算法二　/　79

9.3.4.優化算法三　/　80

9.3.5.優化算法四　/　80

9.3.6.貪心算法　/　81

9.4.唱片錄制　/　82

9.4.1.動態規劃算法一　/　83

9.4.2.動態規劃算法二　/　84

9.4.3.動態規劃算法三　/　85

9.5.相遇問題　/　86

9.5.1.動態規劃算法　/　87

9.5.2.普通遞歸算法　/　89

9.5.3.優化遞歸算法　/　91

9.5.4.寬度優先搜索算法　/　92

9.5.5.動態規劃算法的優化　/　93

9.6.拓展與練習　/　96

 

第 10章 最大連續子序列問題

10.1.最大連續子序列和　/　97

10.2.最大連續子序列積　/　98

10.3.k個最大連續子序列和　/　99

10.4.拓展與練習　/　101

 

第 11章 子矩陣問題

11.1.二維最大子矩陣問題　/　102

11.2.擴展最大子矩陣問題　/　104

11.3.子矩陣變形問題　/　105

11.4.拓展與練習　/　107

 

第 12章 子序列問題

12.1.最長前綴　/　108

12.2.zipper　/　110

12.3.最長公共子序列　/　111

12.3.1.動態規劃算法一　/　112

12.3.2.動態規劃算法二　/　115

12.4.確定基因功能　/　115

12.5.最長公共上升子序列　/　118

12.5.1.基本算法　/　119

12.5.2.優化算法　/　120

12.6.拓展與練習　/　122

 

 

第 13章 雙重動態規劃

13.1.城市交通　/　123

13.2.復雜的審批　/　126

13.3.拓展與練習　/　128

 

第 14章 多進程動態規劃

14.1.方格取數　/　129

14.2.三取方格數　/　132

14.3.拓展與練習　/　134

 

第 15章 樹形動態規劃

15.1.加分二叉樹　/　135

15.2.寶藏　/　137

15.3.選課　/　141

15.4.沒有上司的舞會　/　144

15.5.拓展與練習　/　146

 

第 16章 數碼動態規劃

16.1.包含49　/　147

16.2.幸運數字　/　152

16.3.拓展與練習　/　155

 

第 17章 狀態壓縮動態規劃

17.1.混亂的隊伍　/　156

17.2.放置猛獸一　/　158

17.3.放置猛獸二　/　160

17.4.炮兵陣地　/　162

17.5.清掃計劃　/　164

17.6.拓展與練習　/　166

 

第 18章 動態規劃的高級優化

18.1.單調隊列優化　/　167

18.1.1.最大子序列和　/　167

18.1.2.烽火傳遞　/　169

18.1.3.多重背包　/　171

18.1.4.紀念手錶　/　174

18.2.四邊形不等式優化　/　175

18.2.1.歸並石子3　/　175

18.2.2.破壞鐵路　/　178

18.2.3.分段　/　179

18.3.斜率優化　/　180

18.4.拓展與練習　/　184

 

第 19章 綜合訓練

19.1.逢低吸納　/　185

19.2.紅牌　/　186

19.3.點菜　/　187

19.4.選數統計　/　187

19.5.烏龜棋　/　188

19.6.守望者的逃離　/　189

19.7.三角形最大面積　/　190

19.8.積木游戲　/　191

19.9.多米諾骨牌　/　192

19.10.最大子樹和　/　193

19.11.訪問美術館　/　194

19.12.花園　/　194

19.13.旅行計劃　/　195

19.14.垃圾井　/　196

19.15.重建道路　/　197

19.16.迎接儀式　/　198

19.17.棋盤製作　/　199

19.18.打磚塊　/　200

19.19.血緣關系　/　201

19.20.集合方案數　/　202

19.21.基因序列　/　203

19.22.基因武器　/　204

19.23.壓路機　/　204

19.24.旅行商　/　206

19.25.二叉蘋果樹　/　207

19.26.技能樹　/　208

19.27.騎士　/　209

19.28.猛獸動物園　/　210