一些DP相关 ​

换根DP ​

• 计数DP：直接容斥法
• 最值DP：维护最大次大值法，前后缀合并法

树上连通块DP ​

• 法一：直接DP，在过程中钦定当前点为最浅点
• 法二：基于DP插入复杂度小于合并复杂度，类似shopping的做法
• 例题：shopping

划分型DP ​

• 处理问题：将一个序列分成两个子序列（染两种颜色），然后要满足某些限制
• DP式通常形如：
  • $dp[i][j] \leftarrow dp[i - 1][j]$
  • $dp[i][i - 1] \leftarrow dp[i - 1][j]$
• 注意：应熟知此类DP是很好优化的

例题 ​

• CF1849F
• P11233
• CF1647F

$\min(f(l,i),f(i,r))$ 的处理 ​

• 首先：$f$ 应该有不严格单调性
• 然后常见的，有两种处理办法：
  • 双指针：钦定左边大于右边，然后答案必然只从两分界点中取
  • 二分：
    • 根据左边和右边的大小做二分
    • 当左右相等时必然最优（剪枝）
    • 可以用不常用写法

例题 ​

太多了，懒得找

处理DP的二维价值 ​

基本处理办法 ​

把一维价值也设入状态中，转换成背包问题

常见剪枝 ​

只存下有值的状态，在转移完做一下单调性剪枝

• 相关研究：
  • 其不能直接降低复杂度（基本量级不变）
  • 但是，转移次数越多，转移越复杂，可以除以的常数越大
  • 其算法瓶颈通常在枚举状态进行转移，以及后续的剪枝（考虑算法时间时主要考虑这一点）

特别的优化办法 ​

• 分析DP性质，去掉一维价值
• 直接贪心，考虑怎么选
• 换做法

例题 ​

• AGC035D

例题 ​

P9051：

• 首先二分转判定
• 朴素的DP有两维价值，但注意到DP的第一维价值后面都不会用到
• 那么，我们可以直接在求出第一维价值时就判定是否大于 $mid$
• 这样只用保留一维价值

值域定义域互换 ​

适用范围 ​

最优化DP状态的优化，DP值有单调性

注意点 ​

• 在互换后，一般状态都不能设“恰好”
• 保证得到的DP值是当前答案等于或劣于状态中的答案

例题 ​

LIS ​

• 可以直接设 $dp_i$ 表示LIS长度为 $i$ 的最小的结尾值，$dp$ 初始为 $inf$
• 然后每次扫进新数 $x$，就在 $dp$ 数组里找到 $\geq x$ 的第一个位置，$chkmin(dp,x)$ 即可
• 可以发现，某种程度上这避免了离散化
• practice: [ABC360G] Suitable Edit for LIS

ABC364E Maximum Glutton ​

• 观察到 $N$ 很小，但是对于搜索剪枝来说又不够小（一般应该是30 - 40, 40 - 50可能是折半）
• 直接做，显然是二维的背包，但是状态太大了，显得很冗余
• 因为此题是经典DP题（显然不能贪心），所以仍考虑优化DP
• 观察到值域其实只有 $N$ 的，而且有单调性，所以值域定义域互换即可

1D/1D ​

自己规定了在线转移和非在线转移两个概念

简化DP转移 ​

给DP分层，或给DP的转移分类，从而转化成1D/1D问题

决策单调性 ​

适用场景 ​

没有其他思路，只有一个DP，而且没法用其他优化

验证方法 ​

暴力跑随机数据看决策点是否单调

实现方法 ​

• 决策栈 + 二分：处理在线转移
• 分治：处理非在线转移

PS ​

• 有的斜率优化可能表现出了决策单调性
• 有的决策单调性是因为有凸性，此时也可以用下述的优化

凸性相关 ​

前置知识 ​

如何发现DP的凸性 ​

• 满足四边形不等式的序列划分问题的答案（一定是）
• 转移每次加上一个凸函数（较有可能是）
• 直观理解很凸（较可能是）
• 费用流建模（一定是）
• 其他验证方法：暴力跑随机数据验证

常见算法 ​

闵可夫斯基和 ​

• 转移是 $(\max, +)$ 卷积
• 具体而言，要求DP是非在线转移
• 经典的，其可以优化背包合并

wqs二分 ​

• 答案求“恰 $k$ 个”
• 可以直接去掉表示选多少个的那一维（背包DP）

slope trick ​

• 核心：利用凸性动态维护DP数组
• 处理过程：
  • 将DP数组转换成单调的，方便维护（差分数组单调且均非负）
  • 使用DS维护对DP数组的操作，通常维护的是差分数组和其首项（或某一项）

一些要分析DP数组形态的题 ​

Sonya and Problem Wihtout a Legend ​

solution1:

• 有暴力DP，没什么贪心的思路，可以继续优化DP
• DP形如凸函数加起来，猜一个凸
• 确实，所以维护一下差分，注意修改时保证始终 $\geq 0$
• 最后要维护一个实际DP值才能用差分推出答案，随便取一个即可

solution2:

• 序列递增，直接差分，发现就是要让差分数组全变成 $> 0$
• 操作每次会将差分的一个数 $++$，下一个数 $--$，或是相反
• 很流，可以费用流，竟然过了

P9051 ​

• 经典凸性转移形式：网格图两种走法求最短路
• 处理：
  • 考虑直接维护差分数组及首项
  • 首项是好处理的
  • 差分数组每次直接插入一个数就可以了
  • 剩下的一些细节就特殊处理