Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P3216\":[\"数学作业\",2909,\"HNOI2011\"],\"洛谷-P2886\":[\"Cow Relays G\",4463,\"USACO07NOV\"],\"洛谷-P2566\":[\"围豆豆\",558,\"SCOI2009\"],\"CodeForces-1009F\":[\"Dominant Indices\",5517,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1009\\\"\\u003eEducational Codeforces Round 47 (Rated for Div. 2)\\u003c/a\\u003e\"],\"洛谷-P2569\":[\"股票交易\",5752,\"SCOI2010\"],\"洛谷-P2602\":[\"数字计数\",17354,\"ZJOI2010\"],\"洛谷-P1833\":[\"樱花\",19589,null],\"洛谷-P1912\":[\"诗人小G\",3759,\"NOI2009\"],\"洛谷-P2605\":[\"基站选址\",2989,\"ZJOI2010\"],\"CodeForces-1146F\":[\"Leaf Partition\",1121,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1146\\\"\\u003eForethought Future Cup - Elimination Round\\u003c/a\\u003e\"],\"CodeForces-512D\":[\"Fox And Travelling\",982,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/512\\\"\\u003eCodeforces Round 290 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P2052\":[\"道路修建\",7724,\"NOI2011\"],\"洛谷-P2495\":[\"消耗战\",9217,\"SDOI2011\"],\"洛谷-P3146\":[\"248 G\",17960,\"USACO16OPEN\"],\"洛谷-P1880\":[\"石子合并\",61220,\"NOI1995\"],\"洛谷-P3502\":[\"CHO-Hamsters\",712,\"POI2010\"],\"洛谷-P1365\":[\"WJMZBMR打osu! / Easy\",4434,null],\"洛谷-P2014\":[\"选课\",33985,\"CTSC1997\"],\"洛谷-P2016\":[\"战略游戏\",16273,null],\"洛谷-P2657\":[\"windy 数\",20761,\"SCOI2009\"],\"洛谷-P2337\":[\"喵星人的入侵\",1218,\"SCOI2012\"],\"洛谷-P2579\":[\"沼泽鳄鱼\",1525,\"ZJOI2005\"],\"洛谷-P2656\":[\"采蘑菇\",3513,null],\"洛谷-P3349\":[\"小星星\",2113,\"ZJOI2016\"],\"洛谷-P6419\":[\"Kamp\",2006,\"COCI2014-2015#1\"],\"洛谷-P4516\":[\"潜入行动\",3589,\"JSOI2018\"],\"CodeForces-1016F\":[\"Road Projects\",800,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1016\\\"\\u003eEducational Codeforces Round 48 (Rated for Div. 2)\\u003c/a\\u003e\"],\"洛谷-P4719\":[\"\\\"动态 DP\\\"\\u0026动态树分治\",6834,\"模板\"],\"洛谷-P3628\":[\"特别行动队\",7081,\"APIO2010\"],\"洛谷-P3190\":[\"神奇游乐园\",1417,\"HNOI2007\"],\"CodeForces-543D\":[\"Road Improvement\",2689,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/543\\\"\\u003eCodeforces Round 302 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P5056\":[\"插头 DP\",3887,\"模板\"],\"洛谷-P4360\":[\"锯木厂选址\",4160,\"CEOI2004\"],\"洛谷-P1095\":[\"守望者的逃离\",38511,\"NOIP2007 普及组\"],\"洛谷-P3195\":[\"玩具装箱\",13077,\"HNOI2008\"],\"洛谷-P4284\":[\"概率充电器\",2987,\"SHOI2014\"],\"洛谷-P3272\":[\"地板\",769,\"SCOI2011\"],\"洛谷-P1131\":[\"时态同步\",11378,\"ZJOI2007\"],\"洛谷-P3233\":[\"世界树\",2490,\"HNOI2014\"],\"洛谷-P3354\":[\"Riv 河流\",2074,\"IOI2005\"],\"洛谷-P4124\":[\"手机号码\",5998,\"CQOI2016\"],\"洛谷-P2340\":[\"Cow Exhibition G\",6949,\"USACO03FALL\"],\"洛谷-P5658\":[\"括号树\",13085,\"CSP-S2019\"],\"洛谷-P1850\":[\"换教室\",14281,\"NOIP2016 提高组\"],\"洛谷-P1453\":[\"城市环路\",3754,null],\"洛谷-P4767\":[\"邮局\",4333,\"IOI2000\"],\"洛谷-P1654\":[\"OSU!\",7127,null],\"洛谷-P3554\":[\"LUK-Triumphal arch\",1692,\"POI2013\"],\"洛谷-P3478\":[\"STA-Station\",10817,\"POI2008\"],\"洛谷-P2986\":[\"Great Cow Gathering G\",8764,\"USACO10MAR\"],\"洛谷-P2627\":[\"Mowing the Lawn G\",9289,\"USACO11OPEN\"],\"洛谷-P2704\":[\"炮兵阵地\",20673,\"NOI2001\"],\"CodeForces-348D\":[\"Turtles\",1689,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/348\\\"\\u003eCodeforces Round 202 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P3959\":[\"宝藏\",14219,\"NOIP2017 提高组\"],\"CodeForces-449D\":[\"Jzzhu and Numbers\",4376,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/449\\\"\\u003eCodeforces Round 257 (Div. 1)\\u003c/a\\u003e\"],\"CodeForces-219D\":[\"Choosing Capital for Treeland\",9988,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/219\\\"\\u003eCodeforces Round 135 (Div. 2)\\u003c/a\\u003e\"],\"CodeForces-939F\":[\"Cutlet\",975,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/939\\\"\\u003eCodeforces Round 464 (Div. 2)\\u003c/a\\u003e\"],\"洛谷-P4292\":[\"重建计划\",1819,\"WC2010\"],\"洛谷-P4095\":[\"Eden 的新背包问题\",2257,\"HEOI2013\"],\"洛谷-P2150\":[\"寿司晚宴\",4206,\"NOI2015\"],\"洛谷-P3120\":[\"Cow Hopscotch G\",1133,\"USACO15FEB\"],\"洛谷-P4253\":[\"小凸玩密室\",857,\"SCOI2015\"],\"洛谷-P1063\":[\"能量项链\",45803,\"NOIP2006 提高组\"],\"CodeForces-671D\":[\"Roads in Yusland\",1241,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/671\\\"\\u003eCodeforces Round 352 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P1064\":[\"金明的预算方案\",45100,\"NOIP2006 提高组\"],\"洛谷-P3047\":[\"Nearby Cows G\",6228,\"USACO12FEB\"],\"洛谷-P4059\":[\"找爸爸\",2037,\"Code+#1\"],\"洛谷-P5664\":[\"Emiya 家今天的饭\",8645,\"CSP-S2019\"],\"洛谷-P3287\":[\"方伯伯的玉米田\",2677,\"SCOI2014\"],\"洛谷-P5024\":[\"保卫王国\",4810,\"NOIP2018 提高组\"],\"CodeForces-383E\":[\"Vowels\",2978,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/383\\\"\\u003eCodeforces Round 225 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P3842\":[\"线段\",9035,\"TJOI2007\"],\"洛谷-P1541\":[\"乌龟棋\",34236,\"NOIP2010 提高组\"],\"UVA-12991\":[\"Game Rooms\",308,null],\"洛谷-P5904\":[\"HOT-Hotels 加强版\",1913,\"POI2014\"],\"洛谷-P1941\":[\"飞扬的小鸟\",14179,\"NOIP2014 提高组\"],\"洛谷-P2515\":[\"软件安装\",5369,\"HAOI2010\"],\"洛谷-P3647\":[\"连珠线\",1467,\"APIO2014\"],\"CodeForces-149D\":[\"Coloring Brackets\",4951,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/149\\\"\\u003eCodeforces Round 106 (Div. 2)\\u003c/a\\u003e\"],\"CodeForces-311B\":[\"Cats Transport\",3496,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/311\\\"\\u003eCodeforces Round 185 (Div. 1)\\u003c/a\\u003e\"],\"CodeForces-708C\":[\"Centroids\",3172,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/708\\\"\\u003eAIM Tech Round 3 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P6280\":[\"Exercise G\",1034,\"USACO20OPEN\"],\"CodeForces-739E\":[\"Gosha is hunting\",2275,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/739\\\"\\u003eCodeforces Round 381 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P4381\":[\"Island\",3983,\"IOI2008\"],\"洛谷-P3174\":[\"毛毛虫\",4219,\"HAOI2009\"],\"洛谷-P6442\":[\"KOŠARE\",596,\"COCI2011-2012#6\"],\"洛谷-P1272\":[\"重建道路\",7531,null],\"洛谷-P2481\":[\"代码拍卖会\",1012,\"SDOI2010\"],\"洛谷-P3052\":[\"Cows in a Skyscraper G\",7496,\"USACO12MAR\"],\"洛谷-P4262\":[\"白金元首与莫斯科\",413,\"Code+#3\"],\"洛谷-P1273\":[\"有线电视网\",15596,null],\"洛谷-P4342\":[\"Polygon\",5761,\"IOI1998\"],\"洛谷-P1077\":[\"摆花\",54503,\"NOIP2012 普及组\"],\"洛谷-P1352\":[\"没有上司的舞会\",49829,null]}","joined":false,"groups":{}},"managingGroups":{},"author":"Isun","updateTime":1697316334000,"title":"【动态规划】普及~省选的dp题","dislikeCnt":0,"content":"Source: https://www.luogu.com.cn/training/1435\n\u003chr\u003e\n[之前的题单](https://www.luogu.com.cn/paste/k45854e7)\n\n### 0x0 change log\n+ 题单于 2020-7-2 重构完成,分成版块并添加了新的题目\n\t+ 如有其余好的dp题欢迎私信我,如有错误欢迎指出\n\t+ 题单的题目列表请以题单描述中的题目为准,新版题单中的题目列表还没有更新\n+ 2020-7-4 加入了树形dp综合练习题,其他版块新增 2 道题\n+ 2020-7-12 更新了「分治法」版块,撤下了题目编排中的题;由于题目数量限制后面会以每个版块单独的题单呈现\n+ 2020-7-16 子题单施工完毕,已经添加链接\n+ 2020-8-23 更新了「状压dp」「区间dp」,加入了「长链剖分」 \n+ 2020-10-21 加入了一些题目,新增「子集dp」「数据结构优化dp」「缩点」\n\n本题单共 96 题\n\n### 0x1 暴力dp\n别考虑优化,推出方程直接AC\n\n这部分的子题单:[「0x1 暴力dp」](https://www.luogu.com.cn/training/13993)\n#### 0x10 线性dp\n大多思维难度不高,也不需要啥优化,是基础的dp练手题\n\n[problem:洛谷-P1095] 普通的线性dp,简单的分类讨论就好了 \n[problem:洛谷-P1077] 计数类dp,甚至不需要分类讨论 \n[problem:洛谷-P3842] 线性dp,不过是要分类讨论 \n[problem:洛谷-P1541] 暴力dp,很裸的题 \n[problem:洛谷-P4059] 暴力dp,按照末尾空格分类\n\n---\n#### 0x11 背包问题\n题目中大多有价值和体积,有些时候也要把题目转化成价值和体积的模型\n\n[problem:洛谷-P1833] 多重背包模板 \n[problem:洛谷-P1064] 带有附带物品的背包问题,为树上背包打基础 \n[problem:洛谷-P1941] 背包建模 \n[problem:洛谷-P2340] 巧妙的背包问题\u0026amp;分类讨论 \n\n\n---\n#### 0x12 区间dp\n状态大多为一个区间\n\n[problem:洛谷-P1880] 简单的区间dp,配合断环成链的技巧就行啦 \n[problem:洛谷-P3146] 和上题类似,也是区间dp \n[problem:洛谷-P1063] 经典的区间dp \n[problem:洛谷-P4342] 区间dp+断环成链 \n[problem:CodeForces-149D] 区间dp,特殊的转移方式 \n[problem:UVA-12991] 区间 dp 的思想引出正解\n\n---\n#### 0x13 状压dp\n将状态压缩成一个任意进制的数进行dp,适用于数据范围小的dp\n\n[problem:洛谷-P3052] 状压dp+枚举状态的子集 \n[problem:洛谷-P2704] 状压dp+空间优化 \n[problem:洛谷-P3959] 状压dp,按层转移 \n[problem:洛谷-P2150] 隐藏的数据范围 \n[problem:洛谷-P2566] 状压dp+计算几何技巧\n\n---\n棋盘上还有按格转移的状压dp,可以节省一点时间复杂度,代码量较大\n\n[problem:洛谷-P3272] 插头dp入门题 \n[problem:洛谷-P3190] 也是插头dp入门题 \n[problem:洛谷-P5056] 哈密尔顿回路,比较困难的插头dp \n[problem:洛谷-P4262] 带有技巧性的插头/轮廓线dp \n[problem:洛谷-P2337] 复杂的插头dp \n\n---\n#### 0x14 数位dp\n对于数进行dp\n\n[problem:洛谷-P2657] \n[problem:洛谷-P4124] \n[problem:洛谷-P2602] \n↑都是数位dp入门题↑\n\n[problem:洛谷-P2481] 带有技巧性的数位dp\n\n---\n### 0x2 树形dp\nNOIp/csp 常考类型,最重要的dp\n\n这部分的子题单:[「0x2 树形dp」](https://www.luogu.com.cn/training/13994)\n\n#### 0x20 基础的树dp\n没什么难度,入门级别的题目\n\n[problem:洛谷-P1352] 最大权独立集问题 \n[problem:洛谷-P2016] 最小权覆盖集问题 \n\n---\n#### 0x21 树上背包\n有依赖性的背包\n\n[problem:洛谷-P2014] 树上背包模板 \n[problem:洛谷-P1273] 树上背包经典题 \n[problem:洛谷-P1272] 类似树上背包的树形dp \n[problem:洛谷-P3354] 树上背包,也有更快的wqs二分做法 \n\n---\n#### 0x22 二次扫描法\n也叫换根dp,一般第一次扫描考虑子树内的贡献,第二次扫描考虑子树外/全局的贡献\n\n[problem:洛谷-P3478] 换根dp模板题 \n[problem:洛谷-P2986] 换根dp模板题 \n[problem:洛谷-P3047] 换根dp,也有其他的方法 \n[problem:CodeForces-708C] 换根dp好题 \n[problem:洛谷-P6419] 分类讨论较麻烦的换根dp(听说被lswn分类3种吊打了/youl) \n[problem:洛谷-P3647] 比较困难的换根dp \n\n---\n#### 0x23 基环树\n$n$ 条边 $n$ 个点,突破口就在环上\n\n[problem:洛谷-P1453] 基环树上最大权独立集问题 \n[problem:洛谷-P4381] 基环树直径问题 \n\n---\n#### 0x24 虚树\n多次询问询问,总点数不多时可以去掉一些无用的点把时间复杂度优化到 $\\Theta(n\\log n)$\n\n[problem:洛谷-P2495] 虚树dp模板题 \n[problem:洛谷-P3233] 虚树dp比较难的题 \n\n---\n#### 0x25 长链剖分\n当 dp 状态只和深度有关的时候可以通过长链剖分优化到均摊 $\\Theta (1)$ 的复杂度\n\n[problem:CodeForces-1009F] 长链剖分模板 \n[problem:洛谷-P5904] 神仙 dp+长链剖分优化 \n[problem:洛谷-P4292] 01 分数规划+线段树维护长链剖分\n\n---\n#### 0x26 树形dp综合练习-part1\n比较简单基础的题\n\n[problem:洛谷-P3174] \n[problem:洛谷-P3554] \n[problem:CodeForces-219D] \n[problem:洛谷-P1131] \n[problem:洛谷-P2052] \n[problem:洛谷-P5658] \n\n---\n#### 0x27 树形dp综合练习-part2\n稍微难一点的树dp\n\n[problem:洛谷-P4253] \n[problem:洛谷-P4516] \n[problem:CodeForces-512D] \n[problem:CodeForces-543D] \n[problem:CodeForces-1146F] \n[problem:CodeForces-1016F] \n[problem:CodeForces-671D]\n\n---\n### 0x3 dp 优化\n有些时候暴力 dp 不再适用了,于是需要一些优化\n\n这部分的子题单:[「0x3 dp优化」](https://www.luogu.com.cn/training/14005)\n\n#### 0x30 单调队列优化\n「一个人要是比你小,还比你强,那你就永远打不过他了」——单调队列\n\n[problem:洛谷-P2627] \n[problem:洛谷-P2569] \n都比较模板,一般看完转移方程就能看出单调队列的影子 \n[problem:CodeForces-939F] 比较难的单调队列 dp\n\n---\n#### 0x31 决策单调性优化\n当一个转移方程中的价值函数满足四边形不等式时,那么这个方程的决策单调不降,这时就可以用二分+队列来维护\n\n[problem:洛谷-P1912] 决策单调性优化模板题 \n\n---\n#### 0x32 斜率优化\n数形结合,适用于 $f_i\u003d\\min\\{-kx+y\\}$ 形式的方程,用单调队列维护一个凸壳,降低复杂度\n\n[problem:洛谷-P3195] \n[problem:洛谷-P4360] \n[problem:洛谷-P3628] \n[problem:CodeForces-311B] \n↑都是模板题↑\n\n---\n#### 0x33 分治法\n用线段树分治和cdq分治的思想来优化\n\n[problem:洛谷-P4095] 线段树分治+背包 \n[problem:洛谷-P3120] 类cdq分治\n\n---\n#### 0x34 凸优化dp\nwqs二分,给每个物品设置一个代价,从而找到最优解;但是注意函数必须满足凸性\n\n[problem:CodeForces-739E] wqs二分模板题 \n[problem:洛谷-P4767] wqs二分+决策单调性优化 \n\n---\n#### 0x35 矩阵加速\n利用有结合律的矩阵乘法优化,当然矩阵乘法可以是广义的 \n**这部分有部分题目与dp无关**\n\n[problem:洛谷-P2579] 矩阵快速幂+周期 \n[problem:洛谷-P3216] 分段矩阵快速幂 \n[problem:洛谷-P2886] 矩阵加速floyd \n[problem:洛谷-P3502] 广义矩阵快速幂\n\n---\n#### 0x36 动态dp\n数据结构优化资瓷修改的dp\n\n[problem:洛谷-P4719] 动态树上最大权独立集问题 \n[problem:洛谷-P5024] 动态树上最小权覆盖集问题\n\n---\n#### 0x37 容斥原理\n利用容斥优化dp\n\n[problem:洛谷-P5664] 剪去无用状态+补集转化 \n[problem:洛谷-P3349] 容斥+树形dp \n[problem:CodeForces-348D] 不相交路径的经典问题\n\n---\n#### 0x38 子集 dp\n又称 sos dp,利用一种方法将子集求和的复杂度从 $\\Theta(3^n)$ 降到 $\\Theta(2^nn)$\n\n[problem:CodeForces-449D] \n[problem:洛谷-P6442] \n[problem:CodeForces-383E] 均为容斥+sos dp\n\n---\n#### 0x39 数据结构优化 dp\n大多为线段树或者树状数组来优化 dp\n\n[problem:洛谷-P2605] 线段树优化 \n[problem:洛谷-P3287] 二维树状数组优化\n\n---\n#### 0x3A 缩点\n将双联通/强连通分量缩点再按拓扑序进行dp\n\n[problem:洛谷-P2656] 缩点 dp \n[problem:洛谷-P2515] 缩点+树上背包 \n\n---\n### 0x4 数学问题\n数论、期望+dp\n\n这部分的子题单:[「0x4 数学问题」](https://www.luogu.com.cn/training/14006)\n\n#### 0x40 数论dp\n说数论其实也就是一个质数\n\n[problem:洛谷-P6280] 数论+dp \n\n---\n#### 0x41 期望dp\n数学期望的递推\n\n[problem:洛谷-P1365] \n[problem:洛谷-P1654] 这两题均为 combo 的问题 \n[problem:洛谷-P1850] 期望dp\u0026amp;floyd \n[problem:洛谷-P4284] 期望dp+换根 ","threadId":173132,"likeCnt":0,"createTime":1697315916000,"isWorkbook":true,"viewCnt":978,"openness":2,"fav":false,"id":4189,"trustable":true}