7.30 DP

凸相关

决策单调性、斜率优化、凸、四边形不等式，都是凸相关。

前置知识

四边形不等式：交叉小于包含。\(l_1<l_2<r_1<r_2\to w(l_1,r_1)+w(l_2,r_2)\leq w(l_1,r_2)+w(l_2,r_1)\)。

区间包含单调性：包含区间值单调。\(l_1<l_2<r_2<l_1\to w(l_1,r_1)\geq w(l_2,r_2)\)。

满足四边性不等式的 \(w\)，在外面套一个凸函数（一阶导数单调增加的函数，例如平方），还是四边形不等式。

若有 \(w(l,r)=f(r)-g(l)\)，则满足四边形恒等式。

参考资料：DP的决策单调性优化总结——command_block。

P4767 [IOI2000] 邮局

2D/1D 的 DP：\(f(i,j)\) 前 \(i\) 个村庄使用了 \(j\) 个邮局的最小代价。\(f(i,j)=\min_k\{f(k,j-1)+w(k+1,i)\}\)。

\(w(l,r)\) 表示强制这个区间的村庄走到中间一个邮局的总代价，显然邮局建在坐标中位数（注意是中位数）即可。\(w\) 满足四边形不等式和区间包含单调性，\(f\) 决策单调性。

2D/1D 暴力决策单调性

\(opt(i,j)\) 表示 \(f(i,j)\) 从哪个 \(k\) 转移得到。\(opt(i,j-1)\leq opt(i,j)\leq opt(i+1,j)\)。为什么这样？考虑在平面直角坐标系中画出来这些点，状态黑点对应决策红点，画出来是一行斜线，总转移量是 \(O(n)\) 的，最后均摊 \(O(n^2)\)。做的时候使 \(opt(i,j)\) 在 \(opt(i,j-1)\) 到 \(opt(i+1,j)\) 枚举，复杂度分析时一个点会被加一次和减一次，剩下的不超过 \(O(n^2)\)。

扩展

结论：满足四边形不等式的 \(w\)，有性质，\(n\) 个物品划分成 \(k\) 段，与划分成 \(k-1\) 段的方案是交错的。在环上时（换起点）也是如此，就是决策点在每个区间中选个点。

P6246 [IOI2000] 邮局 加强版

\(f(k)\) 把 \(n\) 个东西划分成 \(K\) 段 / 选出恰好 \(K\) 个物品的最小代价，越多的段代价越小，同时减少量越少，感性理解就是下凸。WQS 二分斜率 \(k\)，变成 1D/1D 的 DP，\(g(i)=k+\min_j\{g(j)+w(j+1,i)\}\)，然后它又有决策单调性了（不等式两边加两个 \(k\) 没事）。

WQS 二分

WQS 二分本质上就是用斜率 \(k\) 切凸包，假设切了 \((x,y)\)，算出来 \(y-kx\)，这个 \(kx\) 就是多的贡献，于是可以还原真实值。通过判断 \(x\) 与目标 \(K\) 的关系，不断调整斜率最终切到答案。

• 做 \(g\) 的 DP 时，额外记录 \(g\) 取最小值时用了多少个邮局（记录方案，而不是记录在状态中），这样就知道最后切到的 \(x\) 在哪里。

• 有一个边界问题，最后切了很多个点共线，有一种方法是记录切到最小的 \(x_1\)，直到找到最大的 \(x_1\) 满足 \(x_1\leq m\)，用它来更新答案。

• 为什么答案一定是整数？1. \(f(x)\) 为整数 2. \(x\) 的定义域为整数 3. 答案的斜率是两个相邻点连接的线的斜率。所以答案的斜率为整数，即 \(\frac{f(K)-f(K-1)}{1}\)。同时斜率上界为 \(f(x)\) 的上界。

1D/1D 队列维护决策单调性

1D/1D 的 DP 中，维护队列 \((l,r,j)\) 表示 \(f_{i\in[l,r]}\) 都应该由 \(f_j\) 转移而来，\(j\leq l\)。队列中 \(j\) 单调，\([l,r]\) 顺次相连。

1. 欲求 \(f_i\)，那么检查队头 \(r_h<i\) 的 \((l_h,r_h,j_h)\) 的删掉。取出队头进行转移。\(l_h=i\)。
2. 试图插入决策 \(i\) 的时候：
   1. 记队尾为 \((l_t,r_t,j_t)\)。
   2. 如果对于 \(f[l_t]\) 来说，\(i\) 优于 \(j_t\)，删除队尾，\(pos=l_t\)，返回第一步。
   3. 如果对于 \(f[r_t]\) 来说，\(j_t\) 优于 \(i\)，\(pos=r_t+1\)，去往第五步。
   4. 在 \([l_t,r_t]\) 中二分一个 \(pos\)，使得 \(pos\) 往后是 \(i\) 更优，往前是 \(j_t\) 更优，去往第五步。
   5. 插入决策 \((pos,n,i)\)。

这样的总复杂度为 \(O(n\log n)\)。

（这里有一个误区就是做 \(f_i\) 时从 \(f_{i-1}\) 的决策点开始枚举，这样是假的，因为枚举 \([p_{i-1},i]\) 的时候，你拿到最优决策点，并不知道是最优决策点，只能继续枚举）

Gym103860I Reverse LIS

不超过 \(2k+2\) 个 01010101... 交错排列，能用 \(k\) 次 reverse 操作将其改成 00001111（一次操作缩起来两个）。奇数的情况需要开局特判一次，或者认为前面有不存在的零，或者后面有不存在的一。欲求出每个 \(t\in[0,n]\) 的答案，这里感性理解一下它是凸的，但是点值太多不能 WQS 二分。我们分治，处理 \([l,r]\)，先做 \([l,mid],(mid,r]\) 的答案。合并时，设 \(f(0/1,0/1,t)\) 表示 \(t\) 段，左边/右边是 0/1。做类似于 \(f(a,0)*f(0,b)\to f(a,b)\) 的转移，是凸函数的 \((\max,+)\) 的卷积，闵可夫斯基和合并：将所有斜率拿出来归并排序即为答案的斜率。\(O(n\log n)\)。

代码

判定转 DP

大多为设计一个算法用来判定，这个算法包括 dp，贪心，模拟等。然后把目前判定的状态记录下来，也就是记录判定成这种状态的方案数有多少种。难点在于设计判定算法或减少判定所需要记录的东西。

LOJ6274 数字

考虑判定，用四个 bool 表示 \(x,y\) 的状态：\(x,y\) 是否与 \(l,r\) 完全一致（是的就有限制，不是就无限制）。但我们不知道这些 bool 表示是否到达最终答案，所以枚举一位后，获得这十六种状态是否能到达的状态，这些状态可能会暴毙，可能获得新的状态传递，最后如果有一个活下来就是答案。

DP？\(dp[i][S]\) 用 \(S\) 把 \(2^{16}\) 种情况都压起来，爆搜就是了。状态数很少，例如当 \(x\) 有两个 bool 是 true 时，其它 \(x\) 不是这样的就不可能出现（\(l,r\) 的前面这么多位全部相同）。转移出去时，先枚举 \(z\)，再枚举可能的所有 \(x,y\)，枪毙不合法的状态，合法状态 update 一下，继续爆搜。

UOJ748 [UNR#6] 机器人表演

判定答案串 \(T\) 是否合法？考虑拿 \(S\) 进来匹配 \(T\)，记录当前 \(S\) 匹配长度 \(len\)，当前的 \(T\) 的前缀和 \(sum\)，已经搞了 \(i\) 位。记 \(S\) 的前缀和为 \(pre\)（\(0\to 1,1\to -1\)），则那些括号的前缀和为 \(s=sum-pre_{len}\)。

• 如果下一个 \(T\) 的字符为 \(0\)，
  • 如果 \(S_{len+1}=0\)，则 \(len:=len+1,sum:=sum+1\)。
  • 否则拿一个左括号进来，\(sum:=sum+1\)。
• 否则 \(T\) 的那一个字符为 \(1\)，
  • 若 \(S_{len+1}=1\)，\(len:=len+1,sum:=sum-1\)。跳过以下判断。
  • 否则必须拿右括号进来，若 \(s=sum-pre_{len}>0\) 则没事，更新 \(sum:=sum-1\)。
  • 否则拿不进来，反悔，撤销之前匹配的 \(len\)。设 \(link_{len}\) 表示一个地方，跳过去之后 \(S\) 跳过去那一段的和为 \(1\)，则 \(len:=link_{len},sum:=sum+1-1\)。

然后暴力 DP 即可。

AGC022E Median Replace

考虑判定。\(000\) 直接干掉，\(011,001\) 等价于删 \(0,1\)，只剩 \(111\) 删的时候我们赢了。维护 stack，底下一堆 \(1\) 和顶上不超过两个 \(0\)。放 \(0\) 的时候就放，放 \(1\) 的时候如果是 \(01\) 就删，否则存着。最后是若干个 \(1\) 和不超过两个 \(0\) 对线，最多牺牲两个 \(1\) 就能解决问题，但是需要再多一个 \(1\) 垫底。那么可以建立一个有限状态自动机（DFA），接受答案串，判定是否合法，那么在上面的 DP 是简单的。

数据结构优化

UOJ559 [NOI2020] 命运

\(dp(u,i)\) 表示子树 \(u\) 中没被满足的最深的限制在深度 \(i\) 的方案数。考虑合并 \(v,u\)：

• 若枚举 \((u,v)=0\)，则 \(dp(u,i)dp(v,j)\to dp’(u,\max(i,j))\)。
• 若枚举 \((u,v)=1\)，则 \(dp(u,i)dp(v,j)\to dp'(u,i)\)。

有值的 DP 状态不超过 \(n\) 个，所以线段树合并维护 DP 值。需要支持区间乘、区间和。