浅谈动态规划
Content
- 序列 DP
- 区间 DP
- 背包 DP
- 状态压缩 DP
- 树形 DP
- 图上的 DP
- 计数 DP / 概率 DP
- 数位 DP
- 动态 DP
- 数据结构优化 DP
- 斜率优化 DP / 四边形不等式优化 DP
- 容斥原理 DP
- 其它特殊 DP 优化
序列 DP
CF930E Coins Exhibition
一步步推导的序列 DP 好题
P4590 [TJOI2018]游园会（DP 套 DP）
模板级别的 DP 套 DP 练习题
P8497 [NOI2022] 移除石子（DP 套 DP）
这篇题解 写的太 tm 好了，一个字都不想改
UOJ 机器人问题
字符串上的匹配计数问题
区间 DP
P7914 [CSP-S 2021] 括号序列
关于括号序列相关区间 DP 的综合考察
P7962 [NOIP2021] 方差
先找到差分数组凸性，再进行区间 DP
背包 DP
P5664 [CSP-S2019] Emiya 家今天的饭
综合背包与容斥原理的好题
P3354 [IOI2005] Riv 河流（树上背包）
转换 DP 思路再进行转移
状态压缩 DP
P7519 [省选联考 2021 A/B 卷] 滚榜
利用差分优化状压 DP
树形 DP
CF1000G Two-Paths（换根）
换根 DP 预处理链上询问
P8294 [省选联考 2022] 最大权独立集问题
树形 DP 的综合应用
P5024 [NOIP2018 提高组] 保卫王国
利用倍增优化 DP
图上的 DP
ABC261H - Game on Graph
有后效性的博弈论问题
P3232 [HNOI2013]游走（高斯消元）
利用高斯消元解决期望类图上 DP
计数 DP / 概率 DP
AT2704 [AGC019E] Shuffle and Swap
分析交换过程解决问题
XJOI 的某道双错排问题
建立二分图模型处理错排问题
P3750 [六省联考 2017] 分手是祝愿
设置合理的状态计算期望
P3239 [HNOI2015]亚瑟王
期望 DP 模板题
数位 DP
P8440 Aleph-0 (IN 15)
带优化的数位 DP
动态 DP
P3781 [SDOI2017]切树游戏
动态 DP 套 FWT，享受 Coding 的乐趣
HDU7160 DOS Card
线段树 / 动态 DP / 回滚莫队，多种解法计数
CF573D Bear and Cavalry
找规律 + 动态 DP
数据结构优化 DP
P6453 [COCI2008-2009#4] PERIODNI（笛卡尔树）
笛卡尔树上的背包问题
P6773 [NOI2020] 命运（线段树合并）
线段树合并优化 DP 的经典问题
P2305 [NOI2014] 购票（树套树）
树链剖分 + 线段树 + 李超线段树，你值得拥有
斜率优化 DP / 四边形不等式优化 DP
P5468 [NOI2019] 回家路线
图上的斜率优化
XJOI 的某一场树上四边形不等式
带你认识新型数据结构：单调栈树
容斥原理 DP
P8292 [省选联考 2022] 卡牌
容斥原理 + 状态压缩解决问题
AT4352 [ARC101C] Ribbons on Tree
容斥原理 + 树上背包解决问题
其它特殊 DP 优化
P6772 [NOI2020] 美食家（矩阵优化）
矩阵优化图上 DP 的模板
P8292 [省选联考 2022] 卡牌（FWT）
不会容斥原理？来试试 FWT 吧！
CF321E Ciel and Gondolas（wqs 二分）
四边形不等式也能解决
P8290 [省选联考 2022] 填树（拉格朗日插值）
意想不到的优化方式