DP的优化
形式优化
有时在解决DP问题时会遇到时间或空间复杂度过高的情况，这时候从DP的形式上进行优化是从根本上改进复杂度，典型的处理方式有预处理、分阶段DP等：
- 预处理：在DP过程中出现的大量重复的计算，往往可以通过预处理来节省重复计算的时间，通常我们在DP前预处理，或者在DP过程中处理出最值。
- 分阶段DP：在某些DP中将DP拆分成若干个不相关的转移，分开考虑，也许可以降低复杂度。
例题一、最长公共子序列
给定长度为N,M的数组A,B，求最长公共上升子序列的长度。
$N,M\le 5000$
Solution
设dp[i,j]表示数组A考虑到i，数组B考虑到j且以B[j]结尾的最长公共上升子序列长度。
那么显然，当$A_i=B_j$时，我们有$dp[i][j] = \max\{dp[i-1][k]|k<j,B_k<B_j\}+1$
但是呢，这样转移总时间复杂度是$O(n^3)$的，因此我们需要对我们的DP形式进行优化。
考虑到$A_i=B_j$，那么实际上对于同一个$A_i$，对k的限制是相同的，因此我们只需要在枚举j的过程中动态维护$\max\{dp[i-1][k]|B_k<A_i\}$，直接转移即可。
决策单调性优化
四边形不等式优化
对于如下形式的dp：
若$w$满足四边形不等式：
- 任意$i\le i’\le j\le j’$，有$w_{i,j}+w_{i’,j’}\le w_{i’,j} + w_{i,j’}$
- 任意$i’\le i\le j\le j’$，有$w_{i,j}\le w_{i’,j’}$
则
可得$f(i,j)$的决策一定在$f(i,j-1)$的决策与$f(i-1,j)$的决策之间。
1D/1D动态规划方程优化
对于形如
若$w$满足四边形不等式，则$f(i)$的决策也一定单调。
这里的决策也就是j的实际取值
例题一、诗人小G
Solution
由题意推得
令$w_{i,j}=\left|sum_j-sum_i+(j-i-1)-L\right|^p$，接下来我们来证明$w$满足四边形不等式
即证$w_{i,j}+w_{i+1,j+1}\le w_{i+1,j}+w_{i,j+1}$
令$u=sum_j+j-(sum_i+i)-(1+L)$，$v=sum_j+j-(sum_i+a[i]+j+1)-(1+L)$
则即证$\left|v\right|^p-\left|v+a_{i+1}+1\right|^p\ge\left|u\right|^p-\left|u+a_{i+1}+1\right|^p$
因此只需证明$\left|x\right|^p-\left|x+c\right|^p,c\in [0,+\infty)$是单调不升函数，分类讨论即可
所以对于任意的$i\le j$，$f(i)$的决策一定小于等于$f(j)$的决策，于是我们用单调栈或单调队列来维护决策点。
每次将旧的决策与新决策比较时，可能有下面几种情况：
- 旧决策完全不如新决策，即选择旧决策的区间的左端点选新决策更优
- 旧决策中有一部分（必然是一个后缀）选新决策更优
- 新决策完全不如旧决策
对于第一种情况，我们直接把旧决策的区间合并到新决策的区间上，任何继续比较下一个旧决策
对于第二种情况，我们直接在旧决策区间上二分找到转折点，将右边的部分全都合并到新决策区间上，更新到这里就中止了
对于第三种情况，直接停止更新
1 | ld dp2[N], sum2[N]; |
斜率优化
斜率优化是当DP转移式形如
将与j无关的常数提出来，我们就是要求
令$y_j=f(j)+b_j$，则我们要在所有的$y_j=-k_ix_j+B$中找到B最小的，即为答案。
显然最优的$(x_j,y_j)$一定在凸壳（即点集边界）上，通过维护凸壳，可以达到优化复杂度的目的。
根据$x_j$和$k_i$的单调性，我们可以：
例题一、
首先我们设$f(i)$表示打印前i个字符的最小花费，那么显然有
为了方便表示，我们设sum[i]表示$C[k]$的前i项和，则有
那么我们其实就是要求
设$y_j=f(j)+sum[j]^2$，$x_j=sum[j]$
我们假设从j点转移比从k点转移更优且k < j
则有$y_k-2\cdot sum[i]\cdot x_k\ge y_j-2\cdot sum[i]\cdot x_j$
整理得到
由于这里i是递增的，所以之后的所有决策中j都一定比k更优，因此可以将k直接排除掉，只保留j。
设$g(i,j)=\dfrac{y_i-y_j}{x_i-x_j}$对于$k
- 当$g(i,j)\le 2\cdot sum[i]$时，说明i比j更优，j要被排除
- 当$g(i,j)> 2\cdot sum[i]$时，$g(k,j)>2\cdot sum[i]$，说明k比j更优，j要被排除
所以当$g(k,j)>=g(i,j)$时，我们要排除j。
如此一来，我们维护的是一个下凸壳，这里通常使用单调队列来实现。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25ll dp[N], sum[N];
int q[N];
ll gety(ll x) { return dp[x] + sum[x] * sum[x]; }
ll getx(ll x) { return sum[x]; }
ll getfz(ll j, ll k) { return gety(j) - gety(k); }
ll getfm(ll j, ll k) { return getx(j) - getx(k); }
int main() {
int n, m;
while (~scanf("%d%d", &n, &m)) {
for (int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + fast_IO::read();
for (int i = 1; i <= n; ++i)dp[i] = 0;
int head = 0, tail = 0;
q[tail++] = 0;
for (int i = 1; i <= n; ++i) {
while (head + 1 < tail && getfz(q[head + 1], q[head]) <= 2 * sum[i] * getfm(q[head + 1], q[head]))++head;
dp[i] = dp[q[head]] + (sum[i] - sum[q[head]]) * (sum[i] - sum[q[head]]) + m;
while (head + 1 < tail && getfz(q[tail - 1], q[tail - 2]) * getfm(i, q[tail - 1]) >= getfm(q[tail - 1], q[tail - 2]) * getfz(i, q[tail - 1]))--tail;
q[tail++] = i;
}
fast_IO::write(dp[n]); putchar('\n');
}
return 0;
}
例题二、
同样先设$f(i)$表示前i个任务完成需要的最小费用。
设sum[i]表示前i个任务时间总和，sc[i]表示费用C的前i项和，列出转移式
那么我们就是要求
设$y_j=f(j),x_j=sc[j]$
我们假设从j点转移比从k点转移更优且k < j
则有$y_j-(sum[i]+s)\cdot x_j\le y_k-(sum[i]+s)\cdot x_k$
整理得
由于sum[i]并不一定是单调的，所以我们不能像上面那样直接单调队列解决。
但是与上面相同的是，我们依然需要找到最小的B，也就是说，我们将一条斜率为$sum[i]+s$的直线从下往上移动，遇到的第一个决策点就是最优决策点，因为此时得到的B最小。
可见，我们需要维护的依旧是下凸壳，只不过由于这里直线的斜率不再单调，我们需要二分找到最优决策点。
下凸壳可以用单调栈或单调队列来维护。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28ll dp[N], sum[N], sc[N], s;
int st[N];
ll getfz(int j, int k) { return dp[j] - dp[k]; }
ll getfm(int j, int k) { return sc[j] - sc[k]; }
int main() {
int n = fast_IO::read();
s = fast_IO::read();
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + fast_IO::read();
sc[i] = sc[i - 1] + fast_IO::read();
}
int top = 0;
st[++top] = 0;
for (int i = 1; i <= n; ++i) {
int l = 1, r = top;
while (l <= r) {
int mid = l + r >> 1;
if (getfz(st[mid], st[mid - 1]) <= (sum[i] + s) * getfm(st[mid], st[mid - 1]))l = mid + 1;
else r = mid - 1;
}
dp[i] = dp[st[r]] + sum[i] * (sc[i] - sc[st[r]]) + s * (sc[n] - sc[st[r]]);
while (top > 1 && getfz(st[top], st[top - 1]) * getfm(i, st[top]) >= getfm(st[top], st[top - 1]) * getfz(i, st[top]))--top;
st[++top] = i;
}
fast_IO::write(dp[n]);
return 0;
}
例题三、运输小猫
这个题的难点在于问题的转换。
首先我们记第i座山到第1座山的距离为$d[i]=\sum\limits_{j=2}^{i}D[i]$。
记某饲养员出发时间为$s$，若某只猫要被一个饲养员接到，其充要条件是$s+d[i]\ge t[i]$即$s\ge d[i]-t[i]$。
我们记$a[i]=d[i]-t[i]$，则上述条件为$s\ge a[i]$
仔细考虑一下，这个$a[i]$表示的其实就是饲养员出发的最小时间，显然每个饲养员接走的小猫是在a上连续的，即如果将所有猫按a排序，那么一定存在一种代价最小的方案是将整个区间划分成p份，每个饲养员接走一段上所有的小猫，因为跳过一只小猫的话这只小猫等待的时间会变长，而其他小猫等待的时间不变。而由于饲养员只是简单的从1走到n，等待时间可以用$a$来算。
现在我们来设状态，设dp[i][j]表示i个饲养员接走前j只猫需要的最小代价。
那么我们很容易写出转移方程$dp[i][j]=min\{dp[i-1][k]+(j-k)\times a[j]-\sum\limits_{u=k+1}^{j}a[u]|k<j\}$
稍微解释一下这个方程，第i个饲养员的出发时间我们置为a[j]，任何就可以算出k+1到j的小猫等待时间之和。
设sum为a的前缀和，将转移方程化简$dp[i][j]=min\{dp[i-1][k]+(j-k)\times a[j]-(sum[j]-sum[k])|k<j\}$
进一步变形得到
显然这是一个可以斜率优化的式子，将与k无关的项去除，得到
移项得到
显然设$Y=dp[i-1][k]+sum[k],X=k,K=a[j],B=dp[i][j]$，这里X单调不降，K单调不降，因此是最基础的单调队列维护凸包和转移位置
唯一需要注意的是，转移位置要从i-1处找，而当前的dp值更新的是i处的凸包。
1 | int d[N], q[105][N], head[N], tail[N]; |
凸单调性DP优化
矩阵优化
数据结构优化
容斥DP
SOSDP
(cf的一篇blog)[https://codeforces.com/blog/entry/72488]