中等水平各类dp

**这个题单可以将你的 dp 快速从普及组水平过渡到提高组中上级别水平** **个人认定难度按顺序排序** 题目编排按个人主观难度从易到难排。 ## 第一部分：简单模板dp 本部分 dp 内容较为简单 难度：黄至蓝。 - [P4310 绝世好题](https://www.luogu.com.cn/problem/P4310) [简单dp。代码写起来感觉像状压。官评绿，自评橙黄之间。](https://www.luogu.com.cn/record/81568863) - [P5322 排兵布阵](https://www.luogu.com.cn/problem/P5322) [背包。官评蓝，自评橙黄之间](https://www.luogu.com.cn/record/81993612) - [UVA10534 Wavio Sequence](https://www.luogu.com.cn/problem/UVA10534) [相当于合唱队形。官评蓝，自评黄](https://www.luogu.com.cn/record/83854350) - [P1800 software](https://www.luogu.com.cn/problem/P1800) [可以当二分优化dp模板做。官评蓝，自评黄](https://www.luogu.com.cn/record/81656180) - [P1880 石子合并](https://www.luogu.com.cn/problem/P1880) [环形dp。官评绿，自评黄。可做模板](https://www.luogu.com.cn/record/57642073) - [P1291 百事世界杯之旅](https://www.luogu.com.cn/problem/P1291) [期望dp，官评绿，自评黄，可做模板](https://www.luogu.com.cn/record/76562972) - [P1004 方格取数](https://www.luogu.com.cn/problem/P1004) [多维dp。官评绿，自评黄](https://www.luogu.com.cn/record/76058573) - [P4170 涂色](https://www.luogu.com.cn/problem/P4170) [区间dp。官评绿，自评黄](https://www.luogu.com.cn/record/81987179) - [P1854 花店橱窗布置](https://www.luogu.com.cn/problem/P1854) [好维护。官评绿，自评黄](https://www.luogu.com.cn/record/81686761) - [P2015 二叉苹果树](https://www.luogu.com.cn/problem/P2015) [树形dp。官评绿，自评黄。可当模板做](https://www.luogu.com.cn/record/65805845) - [P2782 友好城市](https://www.luogu.com.cn/problem/P2782) [排序后二分最长上升子序列。官评黄，自评黄](https://www.luogu.com.cn/record/81680437) - [P1439 最长公共子序列](https://www.luogu.com.cn/problem/P1439) [最长上升子序列+二分+离散化。官评绿，自评黄](https://www.luogu.com.cn/record/81324534) - [P2014 选课](https://www.luogu.com.cn/problem/P2014) [经典的树形dp+背包，官评绿，自评黄，可当模板做](https://www.luogu.com.cn/record/65298984) - [P2602 数字计数](https://www.luogu.com.cn/problem/P2602) [经典数位dp，官评蓝，自评黄，可做模板](https://www.luogu.com.cn/record/75240410) - [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) [树形dp。官评绿，自评黄](https://www.luogu.com.cn/record/65307230) - [UVA1437 String Painter](https://www.luogu.com.cn/problem/UVA1437) [涂色问题是此题的子问题。区间dp，好维护。官评蓝，自评黄绿之间](https://www.luogu.com.cn/record/82078080) - [P3080 Cow Run](https://www.luogu.com.cn/problem/P3080) [经典的区间dp，官评蓝，自评黄绿之间，可做模板](https://www.luogu.com.cn/record/81034311) - [P1896 互不侵犯](https://www.luogu.com.cn/problem/P1896) [状压模板题。官评蓝，自评绿，可做模板](https://www.luogu.com.cn/record/70162588) - [P2622 关灯问题II](https://www.luogu.com.cn/problem/P2622) [状压dp。官评蓝，自评蓝绿之间](https://www.luogu.com.cn/record/84989190) - [CF685B Kay and Snowflake](https://www.luogu.com.cn/problem/CF685B) [树的重心，官评绿，自评黄绿之间，可做模板](https://www.luogu.com.cn/record/65307230) ## 第二部分：可攻克的dp 本部分 dp 思路难度较高（主观） 难度：绿到紫 - [CF280C Game On Tree](https://www.luogu.com.cn/problem/CF280C) [可做模板的期望dp，记录树的深度即可。官评蓝，自评黄绿之间](https://www.luogu.com.cn/record/78974419) - [P1725 琪露诺](https://www.luogu.com.cn/problem/P1725) [dp+单调队列优化。官评绿，自评黄绿之间](https://www.luogu.com.cn/record/81164977) - [P4316 绿豆蛙的归宿](https://www.luogu.com.cn/problem/P4316) [难推。离线。官评绿，自评绿](https://www.luogu.com.cn/record/76924271) - [CF607A Chain Reaction](https://www.luogu.com.cn/problem/CF607A) [二分dp，好维护。官评蓝，自评绿](https://www.luogu.com.cn/record/81675085) - [P4265 Snow Boots S](https://www.luogu.com.cn/problem/P4265) [步长排序，以深度为dp状态。官评蓝，自评绿](https://www.luogu.com.cn/record/88061516) - [P2467 地精部落](https://www.luogu.com.cn/problem/P2467) [二进制优化空间进行dp](https://www.luogu.com.cn/record/85766553) - [P4269 Snow Boots G](https://www.luogu.com.cn/problem/P4269) [不是 Snow Boot G的子问题。线段树优化dp](https://www.luogu.com.cn/record/88030112) - [P4302 字符串折叠](https://www.luogu.com.cn/problem/P4302) [区间dp，字符串处理。官评蓝，自评绿](https://www.luogu.com.cn/record/83332308) - [P1613 跑路](https://www.luogu.com.cn/problem/P1613) [倍增处理优化dp。官评绿，自评绿蓝之间](https://www.luogu.com.cn/record/78950069) [P4124 手机号码](https://www.luogu.com.cn/problem/P4124) [数位dp，1e10溢出有点坑，官评紫，自评绿蓝之间](https://www.luogu.com.cn/record/89919254) - [P1654 OSU!](https://www.luogu.com.cn/problem/P1654) [展开三项式式子。离线。官评蓝，自评绿蓝之间](https://www.luogu.com.cn/record/76573444) - [P1772 物流运输](https://www.luogu.com.cn/problem/P1772) [最短路+dp。官评蓝，自评绿蓝之间](https://www.luogu.com.cn/record/81967224) - [P2890 Cheapest Palindrome G](https://www.luogu.com.cn/problem/P2890) [区间dp难想，维护简单。官评蓝，自评蓝](https://www.luogu.com.cn/record/81976931) - [P5839 Moortal Cowmbat G](https://www.luogu.com.cn/problem/P5839) [字符串修改。dp转化：从枚举k到n平方再到转移为i-k的方案。官评蓝，自评蓝](https://www.luogu.com.cn/record/81318602) - [P1070 道路游戏](https://www.luogu.com.cn/problem/P1070) [强dp题。官评蓝，自评蓝](https://www.luogu.com.cn/record/78968561) - [P4158 粉刷匠](https://www.luogu.com.cn/problem/P4158) [维护两个数组分别写一条dp式，难想。线性无优化题。官评紫，自评蓝](https://www.luogu.com.cn/record/81926145) - [P5336 成绩单](https://www.luogu.com.cn/problem/P5336)[两个状态，无需优化的区间dp。官评紫，自评蓝。](https://www.luogu.com.cn/record/82543101) - [P3239 亚瑟王](https://www.luogu.com.cn/problem/P3239)[期望dp。官评紫，自评蓝紫之间](https://www.luogu.com.cn/record/82300039) - [P3574 FAR-FarmCraft](https://www.luogu.com.cn/problem/P3574) [贪心优化决策进行dp，官评紫，自评蓝紫之间。](https://www.luogu.com.cn/record/83482060) - [P2051 中国象棋](https://www.luogu.com.cn/problem/P2051) [计数dp，m种状态的三维dp，分类讨论三种情况，5条式子，官评蓝，自评蓝紫之间](https://www.luogu.com.cn/record/81586130) - [P2900 Land Acquisition G](https://www.luogu.com.cn/problem/P2900) [dp不那么容易看出来，斜率优化极其模板。官评紫，自评蓝紫之间。虽然难度偏向后一版块，但斜率优化仍是需要熟练掌握的知识。因此放入该版块。可做斜率优化模板题](https://www.luogu.com.cn/record/76057693) ## 第三部分：较难想的dp 本部分 dp 较难想 难度：蓝至紫。 - [CF1107E](https://www.luogu.com.cn/problem/CF1107E) [难想的区间dp。官评紫，自评蓝](https://www.luogu.com.cn/record/82931757) - [P2886 Cow Relays G](https://www.luogu.com.cn/problem/P2886) [这道看似图论最短路，实则矩阵快速幂，式子要推一会儿。官评蓝，自评蓝](https://www.luogu.com.cn/record/74852082) - [P2151 HH去散步](https://www.luogu.com.cn/problem/P2151) [同样是看似图论最短路的推式子矩阵快速幂，要推一会儿。官评蓝，自评蓝](https://www.luogu.com.cn/record/74859320) - [P2279 消防局的设立](https://www.luogu.com.cn/problem/P2279) [树形dp。状态多难想。官评蓝，自评蓝](https://www.luogu.com.cn/record/81370456) - [P4441 Retro](https://www.luogu.com.cn/problem/P4441) [区间dp+bfs](https://www.luogu.com.cn/record/81213677) - [P5785 任务安排（批量计划）](https://www.luogu.com.cn/problem/P5785) [斜率优化dp，推起来复杂，但优化比较模板。官评紫，自评蓝紫之间](https://www.luogu.com.cn/record/76455128) - [P3188 梦幻岛宝珠](https://www.luogu.com.cn/problem/P3188) [2的幂次方优化背包，但跟分组背包又有很大不同。算背包里的难题了。官评紫，自评蓝紫之间](https://www.luogu.com.cn/record/82011233) - [P2943 Cleaning Up G](https://www.luogu.com.cn/problem/P2943) [n方很好想，剪枝状态。官评蓝，自评蓝紫之间](https://www.luogu.com.cn/record/81391020) - [P2519 problem a](https://www.luogu.com.cn/problem/P2519) [dp的状态枚举转化后进行dp](https://www.luogu.com.cn/record/81337533) - [P8476 惊蛰](https://www.luogu.com.cn/problem/P8476) [线段树优化dp。官评蓝，自评紫](https://www.luogu.com.cn/record/84611076) - [P4284 概率充电器](https://www.luogu.com.cn/problem/P4284) [边和点的期望处理、化式子，比较复杂。官评紫，自评紫](https://www.luogu.com.cn/record/78988039) - [P4155 国旗计划](https://www.luogu.com.cn/problem/P4155) [区间覆盖+倍增，官评紫，自评紫](https://www.luogu.com.cn/record/77266706)