信息学竞赛宝典 动态规划

目录 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