dp优化

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

函数

f

是下凸的，就等价于

导数单调不降（对于离散函数，就像数组,e.g.

即由点构成的点函数，导函数定义为差分数组，即

f(x)-f(x-1)

)

这是代数意义

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)

在图上能清晰地看出来

这是几何意义

$f$ 的边际效应递增（很少用）

边际效应

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

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

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

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

wqs二分

问题：解恰好

k

的问题，如恰好选

k

个元素，将序列恰好划分为

k

段等。

做法：算出函数的最小值，并通过设置额外的代价（可正可负）将函数旋转（类似），使

k

变成最小值或最小值之一，所以可能有时没法恰好二分到

k

个，因为答案使最小值之一，但不是二分到的最小值

限制：只能在凸函数上，因为凸函数一定能通过旋转将任何一个函数上的点移动成最小值，但凹函数，如

中间那个点无论怎样旋转，始终都不能成为最小值

决策单调性

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

第二个个式子可以分治计算，具体而言，先计算每一层的

mid

，在分治计算两边，因为决策单调性，所以每一层枚举的转移点总数是

n

个，所以复杂度是

O(nlogn)

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

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

超级大杀器

有以下两个结论：

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

前一个结论：我们可以用 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数组的状态中

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

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

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

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

dp专题（2025.6.23）

文章操作