# 套路 & 经验积累 DP

chen_hx · 2022-05-23 21:56:46 · 个人记录

多发现题目的性质，从性质上下手

dp转移可以通过更改顺序来消除一些限制

把dp转移需要的条件写进dp状态里

dp的用途是广泛的，包括计数、最优化、可行性等等，其根本就是利用记忆化避免重复计算

• 看到奇怪的限制应该考虑将其形式化，常规化

• 看到位运算类的性质可以考虑数位 dp

• 一个排列的笛卡尔树唯一，因此关于排列的若干个区间最值限制可以考虑计算笛卡尔树的形态
  CF1580B Mathematics Curriculum

• 如果元素的贡献与区间最小最大值有关，那么考虑使用 min-max分治 ，使每个元素在其左右端点不在同一块的地方被统计，min-max分治 不仅可以计数，也可以求最优化
  P3592 [POI2015] MYJ 【最优化dp】
CF549F Yura and Developers 【计数】

• 阶梯型DP优化&pht转化的巧妙运用
  P6944 [ICPC2018 WF]Gem Island

• 看到要求商最大可以先从 0/1分数规划 开始想，0/1分数规划 不一定仅限于每一个物品才会带来贡献
  P3778 [APIO2017]商旅

• dp的用途很广，甚至可以用来防止重复比较等，看到题目不会做先想dp
  P6764 [APIO2020]粉刷墙壁

• DP具有无后效性的体现：构成DP的每一步决策都只与当前的状态有关，不与前后有关，就比如说给一堆限制，然后可以将这堆限制分类，然后每一类DP，保证在符合之前所有类的限制的情况下满足当前这一类的限制，可以看做是一种分部处理“且”限制的手段
  P5369 [PKUSC2018]最大前缀和

• 考虑生成一个排列的办法：状压目前使用了多少位，枚举下一步拓展谁

• 树形结构很常见，可以用来dp
  SP3734 PERIODNI - Periodni

• 对于树上任意非祖先两点的都会对其lca产生限制，就直接按照dfs下去即可，设计状态的时候直接就是f[i]表示以i为根的子树中，本身已经满足限制的状态，合并的时候考虑不同子树对于根的限制即可

• 最优化dp 转移的决策（转移路径）不一定要存在直接转移，只需要保证存在最优（复合）路径就够了，就是冗余转移优化
  P4762 [CERC2014]Virus synthesis

• 如果若干个集合两两之间的关系要么包含要么不交，那么集合的包含关系可以构成一棵树 CF494C Helping People
P8252 [NOI Online 2022 提高组] 讨论 【神仙lsy的集合划分树】

• 计数题要考虑如何把问题分组，做到不重不漏，比如可以考虑以最大编号或者最原始祖先来区分等等，就是类似于至少=恰好\times至少这种，反正选出来的代表要具有 唯一代表性 ，即可以唯一代表一类情况，且分类重不漏
  P7105 「C.E.L.U-01」门禁 【差一点想出来的题】
CF512D Fox And Travelling【自己想出来的题】

• 权值是乘在一起然后开根的，可以把开根看做在指数上除，然后就变成分数规划问题

• dp 的有效状态实际上是很少的，可以利用上
  CF1584F Strange LCS

• 如果一些情况使得某一位非常小，某一维非常大（只能接受log），那么可以考虑矩阵乘法

• 01背包的合并具有决策单调性

• 有些题目不能完全预处理，那么就可以先预处理出能预处理的，然后把不能直接预处理出来的用已经预处理的算出来，差不多就是部分预处理
  P4133 [BJOI2012]最多的方案

• 计数类问题考虑加乘法原理
  P5664 [CSP-S2019] Emiya 家今天的饭

• 背包问题决策具有无向性
  P4095[HEOI2013]Eden 的新背包问题

  正着做一次，倒着做一次，之后因为无向性就可以把正着做和倒着做的结果合并！！

• 背包问题中交换物品的顺序对结果不影响
  P4141 消失之物

• 对于要求元素不重复的dp，设计状态时可以考虑一个一个的插入元素，过程类似背包

• 计数dp在设计状态的过程其实是在把情况分类的过程，要注意分类的情况之间相互不包含或重叠，以免在统计时把部分情况算重

• 在让gcd最大的问题里的一种dp的阶段性：把最大的质数作为阶段来拓展

• 多个模式串匹配且长度不定的dp可以把模式串放到AC自动机上，接着dp状态就转变成匹配到AC自动机上的某个点时的状态

• 对于dp中的序列问题，如果每个元素的贡献只与其相对的大小关系有关，那么可以把元素换成康托序，同时一个排列与康托序是一一对应的
  CF1542E1 Abnormal Permutation Pairs (easy version)