Part 4.5-4.12 动态规划

## Part 4.5 状态压缩动态规划 > 将一个状态压缩为一个整数（通常为二进制数），就可以在更为方便地进行状态转移的同时，达到节约空间的目的。 - [P2704 [NOI2001]炮兵阵地](https://www.luogu.com.cn/problem/P2704) - [P1879 [USACO06NOV]Corn Fields](https://www.luogu.com.cn/problem/P1879) - [P1896 [SCOI2005]互不侵犯](https://www.luogu.com.cn/problem/P1896) - [P3092 [USACO13NOV]No Change](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]一双木棋](https://www.luogu.com.cn/problem/P4363) - [P5005 中国象棋 - 摆上马](https://www.luogu.com.cn/problem/P5005) - [P2150 [NOI2015]寿司晚宴](https://www.luogu.com.cn/problem/P2150) ## Part 4.6 倍增优化动态规划 > 利用倍增的方式，我们可以将状态转移的效率大大提高。 - [P1613 跑路](https://www.luogu.com.cn/problem/P1613) - [P1081 开车旅行](https://www.luogu.com.cn/problem/P1081) - [P5024 保卫王国](https://www.luogu.com.cn/problem/P5024) ## Part 4.7 数据结构优化动态规划 > 利用数据结构来维护已有信息，也可以达到优化状态转移的目的。 - [P4719 【模板】动态dp](https://www.luogu.com.cn/problem/P4719) - [P4751 动态dp【加强版】](https://www.luogu.com.cn/problem/P4751) - [P3287 [SCOI2014]方伯伯的玉米田](https://www.luogu.com.cn/problem/P3287) - [P2605 [ZJOI2010]基站选址](https://www.luogu.com.cn/problem/P2605) ## Part 4.8 单调队列优化动态规划 > 借助单调队列，排除不可能的决策，可以起到优化状态转移的效果。 - [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776) - [P3089 [USACO13NOV]Pogo-Cow](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](https://www.luogu.com.cn/problem/P4544) - [P5665 划分](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) ## Part 4.9 斜率优化动态规划 > 通过用单调队列维护一个凸壳，来达到优化转移的目的。 - [P2900 [USACO08MAR]Land Acquisition](https://www.luogu.com.cn/problem/P2900) - [P3195 [HNOI2008]玩具装箱](https://www.luogu.com.cn/problem/P3195) - [P3628 [APIO2010]特别行动队](https://www.luogu.com.cn/problem/P3628) - [P3648 [APIO2014]序列分割](https://www.luogu.com.cn/problem/P3648) - [P4027 [NOI2007]货币兑换](https://www.luogu.com.cn/problem/P4027) - [P4360 [CEOI2004]锯木厂选址](https://www.luogu.com.cn/problem/P4360) - [P5468 [NOI2019]回家路线](https://www.luogu.com.cn/problem/P5468) - [P2305 [NOI2014]购票](https://www.luogu.com.cn/problem/P2305) ## Part 4.10 决策单调性优化动态规划 > 利用决策间的递变规律，也能实现优化状态转移的目的。 - [P3515 [POI2011]Lightning Conductor](https://www.luogu.com.cn/problem/P3515) - [P4767 [IOI2000]邮局](https://www.luogu.com.cn/problem/P4767) - [P1912 [NOI2009]诗人小G](https://www.luogu.com.cn/problem/P1912) - [P1973 [NOI2011]Noi嘉年华](https://www.luogu.com.cn/problem/P1973) - [P3724 [AH2017/HNOI2017]大佬](https://www.luogu.com.cn/problem/P3724) - [P5574 [CmdOI2019]任务分配问题](https://www.luogu.com.cn/problem/P5574) ## Part 4.11 数位统计类动态规划 > 统计一个区间中满足条件的数有多少，就是数位统计类动态规划。 - [P2602 [ZJOI2010]数字计数](https://www.luogu.com.cn/problem/P2602) - [P3281 [SCOI2013]数数](https://www.luogu.com.cn/problem/P3281) - [P2518 [HAOI2010]计数](https://www.luogu.com.cn/problem/P2518) - [P2657 [SCOI2009]windy数](https://www.luogu.com.cn/problem/P2657) - [P3286 [SCOI2014]方伯伯的商场之旅](https://www.luogu.com.cn/problem/P3286) - [P4124 [CQOI2016]手机号码](https://www.luogu.com.cn/problem/P4124) - [P4999 烦人的数学作业](https://www.luogu.com.cn/problem/P4999) - [P2606 [ZJOI2010]排列计数](https://www.luogu.com.cn/problem/P2606) - [P4798 [CEOI2015 Day1]卡尔文球锦标赛](https://www.luogu.com.cn/problem/P4798) ## Part 4.12 轮廓线动态规划 > 轮廓线动态规划（即常说的插头 DP）是一种特殊的状压动态规划，通过以轮廓线为状态来实现状态转移。 - [P5056 【模板】插头dp](https://www.luogu.com.cn/problem/P5056) - [P2289 [HNOI2004]邮递员](https://www.luogu.com.cn/problem/P2289) - [P2337 [SCOI2012]喵星人的入侵](https://www.luogu.com.cn/problem/P2337) - [P5347 【XR-1】俄罗斯方块](https://www.luogu.com.cn/problem/P5347)