第五章

# [返回目录](https://www.luogu.com.cn/training/441063) ## 5.1 DP概念和编程方法 ### 例5.1 [Bone Collector](https://acm.hdu.edu.cn/showproblem.php?pid=2602) ## 5.2 经典线性DP问题 ### 例5.2 [ACboy needs your help](https://acm.hdu.edu.cn/showproblem.php?pid=1712) ### 例5.3 [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776)多重背包板题(二进制拆分优化/单调队列优化) ### 一些应用习题: [最少拦截系统](https://acm.hdu.edu.cn/showproblem.php?pid=1257) [编辑距离](https://www.luogu.com.cn/problem/P2758) [724. 最小划分](https://www.lintcode.com/problem/724) [329. 矩阵中的最长递增路径](https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/) [Multiplication Puzzle](http://poj.org/problem?id=1651) #### 课后习题 [P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles](https://www.luogu.com.cn/problem/P1216) [P1020 [NOIP1999 提高组] 导弹拦截](https://www.luogu.com.cn/problem/P1020) [P1091 [NOIP2004 提高组] 合唱队形](https://www.luogu.com.cn/problem/P1091) [P1095 [NOIP2007 普及组] 守望者的逃离](https://www.luogu.com.cn/problem/P1095) [P1541 [NOIP2010 提高组] 乌龟棋](https://www.luogu.com.cn/problem/P1541) [P1868 饥饿的奶牛](https://www.luogu.com.cn/problem/P1868) [P2679 [NOIP2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679) [P2501 [HAOI2006] 数字序列](https://www.luogu.com.cn/problem/P2501) [P3336 [ZJOI2013] 话旧](https://www.luogu.com.cn/problem/P3336) [P3558 [POI2013] BAJ-Bytecomputer](https://www.luogu.com.cn/problem/P3558) [P4158 [SCOI2009] 粉刷匠](https://www.luogu.com.cn/problem/P4158) [P5301 [GXOI/GZOI2019] 宝牌一大堆](https://www.luogu.com.cn/problem/P5301) [poj 1015 Jury Compromise](http://poj.org/problem?id=1015) [poj 3176 Cow Bowling](http://poj.org/problem?id=3176) [poj 1163 The Triangle](http://poj.org/problem?id=1163) [poj 1080 Human Gene Functions](http://poj.org/problem?id=1080) [poj 1159 Palindrome](http://poj.org/problem?id=1159) [poj 1837 Balance](http://poj.org/problem?id=1837) [poj 1276 Cash Machine](http://poj.org/problem?id=1276) [poj 1014 Dividing](http://poj.org/problem?id=1014) ## 5.3 数位统计DP ### 例5.4 [The Counting Problem](http://poj.org/problem?id=2282)/[[ZJOI2010] 数字计数](https://www.luogu.com.cn/problem/P2602) ### 例5.5 [[SCOI2009] windy 数](https://www.luogu.com.cn/problem/P2657) ### 例5.6 [[CQOI2016] 手机号码](https://www.luogu.com.cn/problem/P4124) #### 课后习题: [P4798 [CEOI2015 Day1] 卡尔文球锦标赛](https://www.luogu.com.cn/problem/P4798) [P3281 [SCOI2013] 数数](https://www.luogu.com.cn/problem/P3281) [P2518 [HAOI2010] 计数](https://www.luogu.com.cn/problem/P2518) [P3286 [SCOI2014] 方伯伯的商场之旅](https://www.luogu.com.cn/problem/P3286) [P4999 烦人的数学作业](https://www.luogu.com.cn/problem/P4999) [poj 3252 Round Numbers](http://poj.org/problem?id=3252) ## 5.4 状态压缩DP ### 例5.7 [最短Hamilton路径](https://www.acwing.com/problem/content/description/93/) ### 例5.8 [Mondriaan's Dream](http://poj.org/problem?id=2411) ### 例5.9 [Easy Tree DP?](https://acm.hdu.edu.cn/showproblem.php?pid=4359) ### 例5.10 [Travelling](https://acm.hdu.edu.cn/showproblem.php?pid=3001)三进制状压dp #### 课后习题: [P1433 吃奶酪](https://www.luogu.com.cn/problem/P1433) [P2381 圆圆舞蹈](https://www.luogu.com.cn/problem/P2381) [P2704 [NOI2001] 炮兵阵地](https://www.luogu.com.cn/problem/P2704) [P1879 [USACO06NOV] Corn Fields G](https://www.luogu.com.cn/problem/P1879) [P1896 [SCOI2005] 互不侵犯](https://www.luogu.com.cn/problem/P1896) [P3092 [USACO13NOV] No Change G](https://www.luogu.com.cn/problem/P3092) [P3694 邦邦的大合唱站队](https://www.luogu.com.cn/problem/P3694) [P4925 [1007] Scarlet的字符串不可能这么可爱](https://www.luogu.com.cn/problem/P4925) [P2157 [SDOI2009] 学校食堂](https://www.luogu.com.cn/problem/P2157) [P2167 [SDOI2009] Bill的挑战](https://www.luogu.com.cn/problem/P2167) [P2396 yyy loves Maths VII](https://www.luogu.com.cn/problem/P2396) [P4363 [九省联考 2018] 一双木棋 chess](https://www.luogu.com.cn/problem/P4363) [P5005 中国象棋 - 摆上马](https://www.luogu.com.cn/problem/P5005) [P2150 [NOI2015] 寿司晚宴](https://www.luogu.com.cn/problem/P2150) ## 5.5 区间DP ### 例5.11 [[NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880) ### 例5.12 [String painter](https://acm.hdu.edu.cn/showproblem.php?pid=2476) ### 例5.13 [You Are the One](https://acm.hdu.edu.cn/showproblem.php?pid=4283) ### 例5.14 [F. Rectangle Painting 1](https://codeforces.com/contest/1199/problem/F) #### 课后习题: [力扣动态规划分类题单](https://leetcode.cn/circle/discuss/NfHhXD/) [vjudeg区间DP题单](https://vjudge.net/contest/77874) [P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880) [P3146 [USACO16OPEN] 248 G](https://www.luogu.com.cn/problem/P3146) [P1063 [NOIP2006 提高组] 能量项链](https://www.luogu.com.cn/problem/P1063) [P1005 [NOIP2007 提高组] 矩阵取数游戏](https://www.luogu.com.cn/problem/P1005) [P4170 [CQOI2007] 涂色](https://www.luogu.com.cn/problem/P4170) [P4302 [SCOI2003] 字符串折叠](https://www.luogu.com.cn/problem/P4302) [P2466 [SDOI2008] Sue 的小球](https://www.luogu.com.cn/problem/P2466) ## 5.6 树形DP ### 例5.15 [P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015) ### 例5.16 [没有上司的舞会](https://www.luogu.com.cn/problem/P1352) ### 例5.17 [有线电视网](https://www.luogu.com.cn/problem/P1273)/[TELE](http://poj.org/problem?id=1155) #### 课后习题: [hdu 1520 Anniversary party](https://acm.hdu.edu.cn/showproblem.php?pid=1520) [hdu 2196 Computer](https://acm.hdu.edu.cn/showproblem.php?pid=2196) [hdu 1011 Starship Troopers](https://acm.hdu.edu.cn/showproblem.php?pid=1011) [hdu 1561 The more, The Better](https://acm.hdu.edu.cn/showproblem.php?pid=1561) [hdu 4003 Find Metal Mineral](https://acm.hdu.edu.cn/showproblem.php?pid=4003) [poj 1947 Rebuilding Roads](http://poj.org/problem?id=1947) [poj 2486 Apple Tree](http://poj.org/problem?id=2486) [P4322 [JSOI2016] 最佳团体](https://www.luogu.com.cn/problem/P4322) [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) [P1040 [NOIP2003 提高组] 加分二叉树](https://www.luogu.com.cn/problem/P1040) [P1122 最大子树和](https://www.luogu.com.cn/problem/P1122) [P1273 有线电视网](https://www.luogu.com.cn/problem/P1273) [P2014 [CTSC1997] 选课](https://www.luogu.com.cn/problem/P2014) [P2585 [ZJOI2006] 三色二叉树](https://www.luogu.com.cn/problem/P2585) [P3047 [USACO12FEB] Nearby Cows G](https://www.luogu.com.cn/problem/P3047) [P3698 [CQOI2017] 小Q的棋盘](https://www.luogu.com.cn/problem/P3698) [P5658 [CSP-S2019] 括号树](https://www.luogu.com.cn/problem/P5658) [P2607 [ZJOI2008] 骑士](https://www.luogu.com.cn/problem/P2607) [P3177 [HAOI2015] 树上染色](https://www.luogu.com.cn/problem/P3177) [P4395 [BOI2003] Gem 气垫车](https://www.luogu.com.cn/problem/P4395) [P4516 [JSOI2018] 潜入行动](https://www.luogu.com.cn/problem/P4516) ## 5.7 一般优化 ### 例5.18 [[SCOI2014] 方伯伯的玉米田](https://www.luogu.com.cn/problem/P3287) ### 例5.19 [[ZJOI2010] 基站选址](https://www.luogu.com.cn/problem/P2605)线段树DP优化 ## 5.8 单调队列优化 ### 例5.20 [[USACO11OPEN] Mowing the Lawn G](https://www.luogu.com.cn/problem/P2627) #### 课后习题: [P1725 琪露诺](https://www.luogu.com.cn/problem/P1725) [P3957 [NOIP2017 普及组] 跳房子](https://www.luogu.com.cn/problem/P3957) [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776) [P3089 [USACO13NOV] Pogo-Cow S](https://www.luogu.com.cn/problem/P3089) [P3572 [POI2014] PTA-Little Bird](https://www.luogu.com.cn/problem/P3572) [P3522 [POI2011] TEM-Temperature](https://www.luogu.com.cn/problem/P3522) [P4544 [USACO10NOV] Buying Feed G](https://www.luogu.com.cn/problem/P4544) [P5665 [CSP-S2019] 划分](https://www.luogu.com.cn/problem/P5665) [P1973 [NOI2011] NOI 嘉年华](https://www.luogu.com.cn/problem/P1973) [P2569 [SCOI2010] 股票交易](https://www.luogu.com.cn/problem/P2569) [P4852 yyf hates choukapai](https://www.luogu.com.cn/problem/P4852) [poj 1821 Fence](http://poj.org/problem?id=1821) [poj 2373 Dividing the Path](http://poj.org/problem?id=2373) [poj 3017 Cut the Sequence](http://poj.org/problem?id=3017) [poj 3926 Parade](http://poj.org/problem?id=3926) [hdu 3401 Trade](https://acm.hdu.edu.cn/showproblem.php?pid=3401) [hdu 3514 Queen’s Case](https://acm.hdu.edu.cn/showproblem.php?pid=3514) [hdu 5945 Fxx and game](https://acm.hdu.edu.cn/showproblem.php?pid=5945) ## 5.9 斜率优化/凸壳优化 ### 例5.21 [Print Article](https://acm.hdu.edu.cn/showproblem.php?pid=3507) #### 课后习题: [vjudge斜率DP专题](https://vjudge.net/article/55) [P2900 [USACO08MAR] Land Acquisition G](https://www.luogu.com.cn/problem/P2900) [P3628 [APIO2010] 特别行动队](https://www.luogu.com.cn/problem/P3628) [P3648 [APIO2014] 序列分割](https://www.luogu.com.cn/problem/P3648) [P4360 [CEOI2004] 锯木厂选址](https://www.luogu.com.cn/problem/P4360) [P5468 [NOI2019] 回家路线](https://www.luogu.com.cn/problem/P5468) [P3195 [HNOI2008] 玩具装箱](https://www.luogu.com.cn/problem/P3195) [P4072 [SDOI2016] 征途](https://www.luogu.com.cn/problem/P4072) ## 四边形不等式优化 ### 例5.22 [[NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880) ### 例5.23 [Optimal Binary Search Tree](https://www.luogu.com.cn/problem/UVA10304) #### 课后习题: [hdu 3516 Tree Construction](https://acm.hdu.edu.cn/showproblem.php?pid=3516) [hdu 2829 Lawrence](https://acm.hdu.edu.cn/showproblem.php?pid=2829) [hdu 3506 Monkey Party](https://acm.hdu.edu.cn/showproblem.php?pid=3506) [hdu 3480 Division](https://acm.hdu.edu.cn/showproblem.php?pid=3480) [P1912 [NOI2009] 诗人小G](https://www.luogu.com.cn/problem/P1912) [P4767 [IOI2000] 邮局](https://www.luogu.com.cn/problem/P4767) [P4072 [SDOI2016] 征途](https://www.luogu.com.cn/problem/P4072)