chen_hx
2022-05-23 21:56:46
看到奇怪的限制应该考虑将其形式化，常规化
看到位运算类的性质可以考虑数位 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的集合划分树】
计数题要考虑如何把问题分组，做到不重不漏，比如可以考虑以最大编号或者最原始祖先来区分等等，就是类似于至少=恰好
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)