dp专题（2025.6.23）

· · 个人记录

dp优化

几何体是凸的，当且仅当任意两点的连线的所有点都在几何体内。

函数 f 是下凸的，就等价于

1.

导数单调不降（对于离散函数，就像数组,e.g. 即由点构成的点函数，导函数定义为差分数组，即 f(x)-f(x-1) )

这是代数意义

2. f(x_1)+f(x_2) \ge 2 f(\frac {x1+x2}{2})

相当于任意两点的连线的所有点（自然包括中点）都在函数图像内部，如图 同时，这也是当 a \le b \le c \le d 时， f(a) + f(d) \ge f(b) + f(c) 在图上能清晰地看出来

这是几何意义

边际效应

将同一个新数加入一段长区间，和一段短区间中，长区间的代价更大/小（收益同理），则这个满足边界效应递增/递减（二维边际效应）

实际例子（一维边际效应）：见ppt

二位边际效应与四边形不等式等价，也就是说只要满足将一个数加入长区间比加入短区间代价更大/小，就符合四边形不等式

同时，四边形不等式可以推出决策单调性，决策完全单调性和凸函数

wqs二分

问题 ：解恰好 k 的问题，如恰好选 k 个元素，将序列恰好划分为 k 段等。

做法 ：算出函数的最小值，并通过设置额外的代价（可正可负）将函数旋转（类似），使 k 变成最小值或最小值之一，所以可能有时没法恰好二分到 k 个，因为答案使最小值之一，但不是二分到的最小值

限制 ：只能在凸函数上，因为凸函数一定能通过旋转将任何一个函数上的点移动成最小值，但凹函数，如 中间那个点无论怎样旋转，始终都不能成为最小值

决策单调性

  1. 1D/1D : f_j +w(i,j) \to f_i
  2. 2D/1D : f_{i,j} + w(j,k) \to f_{i+1,j}

第二个个式子可以分治计算，具体而言，先计算每一层的 mid ，在分治计算两边，因为决策单调性，所以每一层枚举的转移点总数是 n 个，所以复杂度是 O(nlogn)

完全单调性 ：对于任意 𝑖<𝑗，在一个前缀中从 𝑖 转移更好，在一个后缀中从 𝑗 转移更好。

当满足完全单调性时，可以用二分队列来优化 1D/1D 问题

超级大杀器

有以下两个结论：

  1. 代价函数符合四边形不等式的划分问题，代价关于段数是凸的。 https://www.cnblogs.com/Itst/p/12805678.html
  2. 代价函数符合四边形不等式的划分问题决策点是完全单调的。

  3. 前一个结论：我们可以用 wqs 二分。 后一个结论：我们可以用二分单调队列单次 dp。 因此，只要代价函数可以 𝑂(1) 计算且符合四边形不等式，这个题就做完了。

斜率优化

学过，不展开

状态设计技巧

先将所有有关的变量塞到状态里，将dp值变成0/1，然后判断哪一维满足单调性，即在这一维小的时候全是0，大的时候全是1，一般选最大的一位丢到dp值里，这样状态就少了一维

同时注意需要保证dp值的单调性，即若 a > b ，则 a+c>b+c ，否则无法dp

判定类dp

首先，对于一类计数问题，要求不重不漏，这是不应该先计算再去重，而应该转化后直接计算

一般将 n 个数中选 m 个数的计数转化为有一个长度为 n-m 的序列填数的计数，这时就需要一个判定，来判定这个数是否是原序列删数得来。

如ppt第一页代码，判定时只用了一个变量 nw ,所以可以丢进dp数组的状态中

在字符串计数类问题中，这是解决的一般方法：

  1. 解决判定问题
  2. 把判定问题所需的变量都记录在数组之中

dp套dp就是内层的一个变量的判定变成了dp数组来判定

状态压缩就是将判定的变量变成一个集合