-
设 表示达到状态 的期望,答案即为 ;
-
设 表示从状态 转到状态 的期望,求答案的时候加起来;
-
遇到求 的时候直接二项式定理设多个 dp 数组,或者考虑 个人同时进行一样的操作;
-
考虑折线图/笛卡尔树;
-
箭头 dp:
设 表示前 个元素,有 段。转移考虑新建段、加入某段的左边/右边、合并两段。
例题:
-
非负整数划分 dp:
非负整数 划分成 个带标号非负整数的方案数。
设 表示 划分成 个带标号非负整数的方案数,那么有 。转移考虑有多少个 的数:
-
折线优化:
考虑某些形如 这样的只和上一列有关的 dp,可以猜想并且经常有:
存在某个 满足
例题:
-
在 dfs 序上 dp:【2025NOI模拟赛19】b酱的果子
一些 dp 状态 & 技巧
- 本文作者: Exber
- 本文链接: https://Rebxe.github.io/post/yi-xie-qi-guai-de-dp-zhuang-tai/
- 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
0%
x
感谢您的支持,我会继续努力的!
扫码打赏,你说多少就多少