【动态规划】提高组的DP问候

DP是提高组的重中之重。 菜鸡 lgswdn 把做到的提高组难度和知识点的一些比较好的dp题整理了一下，希望可以帮到大家qwq。 PS. 对于树形 DP，lgswdn 专门整理了一个 ~~混乱的~~ 题单，戳[这儿](https://www.luogu.com.cn/training/9714)~。 **Caution：这个题单题真的很少，实际上只能带每个版块的入门** --- UPD： 7/10 增加一道背包 DP。 9/27 修复了已知问题。 10/05 增加了一道背包 DP。 11/9 增加了一道状压 DP。但由于 50 题限制，只在描述中有。 --- ## 一 区间 DP 区间 DP 是 DP 中比较基础的一种。一般来说可以设 $f(l,r)$ 为区间 $[l,r]$ 的答案。 [石子合并](https://www.luogu.com.cn/problem/P1880) 最基础的区间 DP 。 [[USACO16OPEN]248 G](https://www.luogu.com.cn/problem/P3146) 和 [[USACO16OPEN]262144 P](https://www.luogu.com.cn/problem/P3147) 前一题较为模板，后一题需要状态优化。 [[HNOI2010]合唱队](https://www.luogu.com.cn/problem/P3205) 状态需要一些改变（具体化）。 [[IOI1998]Polygon](https://www.luogu.com.cn/problem/P4342) 需要分类讨论，80WA 了仔细想一想为什么。 [[SCOI2003]字符串折叠](https://www.luogu.com.cn/problem/P4302) 其实很多字符串题目也是区间 DP。 [[SCOI2007]压缩](https://www.luogu.com.cn/problem/P2470) 和上面那题有些相似但又不一样。 ## 二 背包 DP 01背包是 DP 的经典，但是提高组选手不应该把目光放在这种题身上，而是应该挑战更加高级的背包。 [飞扬的小鸟](https://www.luogu.com.cn/problem/P1941) 背包经典演变问题。 [货币系统](https://www.luogu.com.cn/problem/P5020) 这不是小凯的疑惑！但是这道题还是有一定思维难度的。 [垃圾陷阱](https://www.luogu.com.cn/problem/P1156) 需要一点点思考。可以用刷表法做。 [[BJOI2019]排兵布阵](https://www.luogu.com.cn/problem/P5322) 当你对背包了解了之后，可以用这题练练手。 [CF730J Bottles](https://www.luogu.com.cn/problem/CF730J) 背包一个很小的变化，第一问很简单，第二问需要稍作转换。 [[SHOI2008]循环的债务](https://www.luogu.com.cn/problem/P4026) 打着背包的标签但是还是有点区别的。转移方程比较难一些，状态表示需要用到去除冗余的思想。 [[HNOI2007]梦幻岛宝珠](https://www.luogu.com.cn/problem/P3188) 背包的分组优化+二进制的奇怪 DP 合并。 ## 三 单调队列 单调队列是提高组 DP 优化中的考点。相比于其他优化，单调队列没有那么难。单调队列模板和意义默认都会。 [[USACO11OPEN]Mowing the Lawn G](https://www.luogu.com.cn/problem/P2627) 单调队列优化 DP 比较模板的题目。 [[POI2014]Little Bird](https://www.luogu.com.cn/problem/P3572) 单调队列维护的对象的比较规则中不一定只有一个元素，比如这道题。 [CF1077F Pictures with Kittens](https://www.luogu.com.cn/problem/CF1077F2) 理解上面的题目后，这道题可以作为练手题目。 [[CSPS2019] 划分](https://www.luogu.com.cn/problem/P5665) 建议做这道题的时候，先想 $64$ 分的 DP。最后需要用 一个贪心，而且这个单调队列还不大一样。 [[SBCOI2020] 一直在你身旁](https://www.luogu.com.cn/problem/P6563) $O(n^3)$ DP 很好想，但是（丢张图）  $O(n^2)$ 需要用到一些优化的 Trick。 ## 四 树形DP ### 4.1 普通树形 DP [战略游戏](https://www.luogu.com.cn/problem/P2016) 很简单的树形dp。先想一想在序列上怎么做。 [毛毛虫](https://www.luogu.com.cn/problem/P3174) 进行一定的分类讨论。 [[POI2014]FarmCraft](https://www.luogu.com.cn/problem/P3574) 贪心可以去优化 DP 的转移。 [[POI2011]Dynamite](https://www.luogu.com.cn/problem/P3523) 最大值最小，你想到什么了呢？ ### 4.2 树形背包 [有限电视网](https://www.luogu.com.cn/problem/P1273) 树形背包经典题目。 [选课](https://www.luogu.com.cn/problem/P2014) 同样模板题。 [重建道路](https://www.luogu.com.cn/problem/P1272) 稍微难一点点的树形背包。 [[JSOI2018]潜入行动](https://www.luogu.com.cn/problem/P4516) 同样的套路，但是分类讨论烦了一点。 ### 4.3 基环树 [城市环路](https://www.luogu.com.cn/problem/P1453) 基环树 DP 模板题。 [[ZJOI2008]骑士](https://www.luogu.com.cn/problem/P2607) 加强版的题目。 [[IOI2008]Island](https://www.luogu.com.cn/problem/P4381) 基环树直径，需要单调队列优化。 ### 4.4 二次扫描/换根DP [[POI2008]Station](https://www.luogu.com.cn/problem/P3478) 模板题一 [CF1092F Tree with Maximum Cost](https://www.luogu.com.cn/problem/CF1092F) 难道上一题加权就不会了吗。 [[USACO10MAR]Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986) 模板题二 [CF708C Centroids](https://www.luogu.com.cn/problem/CF708C) 模型转换，换根DP。 [[APIO2014]连珠线](https://www.luogu.com.cn/problem/P3647) 一道比较难的换根DP。 ## 五 期望DP/概率DP 提高组的期望 DP 一般都不难。提高组中有期望在的，除了数学推导，模型转换就是DP。 [OSU!](https://www.luogu.com.cn/problem/P1654) 期望 DP 的经典题目。 [换教室](https://www.luogu.com.cn/problem/P1850) 提高组期望 DP 真题。 [[SHOI2014]概率充电器](https://www.luogu.com.cn/problem/P4284) 换根 DP 中的期望 DP，难度不小。 ## 六 DP 混杂在一起 一个略微综合的板块，但是不是很难。 [[SCOI2009]粉刷匠](https://www.luogu.com.cn/problem/P4158) 背包DP&区间DP。 [[ZJOI2006]物流运输](https://www.luogu.com.cn/problem/P1772) 区间DP&最短路。 ## 七 状压DP 状压DP的第一个用处是正经做题，第二个用处是一种很常见的暴力。 [[USACO06NOV]Corn Fields G](https://www.luogu.com.cn/problem/P1879) 最模板的板子题。 [[NOI2001]炮兵阵地](https://www.luogu.com.cn/problem/P2704) 上古的 NOI 状压板子二。 [宝藏](https://www.luogu.com.cn/problem/P3959) 提高组考过的真题 [[USACO12MAR]Cows in a Skyscraper G](https://www.luogu.com.cn/problem/P3052) 状态压缩中枚举子集。 [[APIO2007]动物园](https://www.luogu.com.cn/problem/P3622) 数据范围没有状压的标志，但是题目中却另有一个可以状压的东西。有很多有趣的小技巧。 ## 八 小测验 一个的 DP 题组成的小测验，建议上述题做完后来 AK。（注意：题目顺序对应了大致难度排序） T1 [能量项链](https://www.luogu.com.cn/problem/P1063) T2 [子串](https://www.luogu.com.cn/problem/P2679) T3 [Promis I Can't Keep](https://www.luogu.com.cn/problem/P6554) T4 [(POI)Triumphal arch](https://www.luogu.com.cn/problem/P3554) T5 [Emiya家今天的饭](https://www.luogu.com.cn/problem/P5664) T6 [(POI)Hotel](https://www.luogu.com.cn/problem/P3565) （放在第六题主要原因，建议去思考一下长链剖分的做法）