【复习笔记】Week 3 动态规划
NCC79601
2019-11-02 22:27:23
# DAY 1
以下用$w[i]$表示重量 / 体积，$v[i]$表示价值。
## 01 背包
$$f[i][j]=\max\{f[i-1][j-w[i]]+v[i]\}$$
当然，在没有限制的情况下也可以把第一维滚掉：
$$f[j]=\max\{f[j-w[i]]+v[i]\}$$
在这种情况下，需要倒序枚举$j$的值。
### 满背包问题
如果题目要求把背包装满，则可以把所有$f[i]$设为$-\infty$，表示背包体积为$f[i]$时无解；然后令$f[0]=0$，再进行转移。每次转移时判断前驱状态$f[j-w[i]]$是否有解，只在有解的情况下发生转移。
## 多重背包
### 二进制拆分法
把物品个数$c[i]$二进制拆分，比如：$c[i]=13$，则拆分为$1,2,4$倍的物品，即可表示$[0,7]$范围内的所有数；再拆分一个$13-7=6$倍的物品，即可表示$[6,13]$范围内的所有数，因此$[0,13]$内所有的数都得到表示，且拆分出来的物品的和不会超过$c[i]$倍。
### 单调队列优化
可以考虑到，既然每个物品都有确定的体积，那么在转移的时候，一种状态$f[j]$的值只与 下标和$j$对$w[i]$余数相同 的状态相关，那么可以考虑节省掉多余的一些枚举。
首先写出朴素转移方程：$f[i][j]=\max\{f[i-1][j-k\cdot w[i]]+k\cdot v[i]\}$，很显然$f[i][\cdots]$只与$f[i-1][\cdots]$相关，因此可以把第一维滚动掉，设滚动数组为$g[i]$；设一个决策$k$比当前决策$k_0$更优，则有：
$$g[j-k\cdot w[i]]+k\cdot v[i]>g[j-k_0\cdot w[i]]+k_0\cdot v[i]$$
$$\Rightarrow g[j-k\cdot w[i]]-g[j-k_0\cdot w[i]]>v[i]\cdot(k_0-k)$$
由于$j-k\cdot w[i]\equiv j-k_0\cdot w[i](\mod w[i])$，所以每次枚举余数相同的$j$即可；而对于这个不等式，可以想到用 **单调队列** 来维护，具体为：先把不合要求（选了超过$c[i]$个数）的状态出队，然后通过上面的不等式维护弹掉队尾，将当前状态装入单调队列之后，再进行决策。**这几步的顺序差异会导致答案出错**，具体只能感性理解。
```cpp
// https://www.luogu.org/problem/P1776
#include <bits/stdc++.h>
using namespace std;
const int MAXW = 4e4 + 10;
int n, m, f[MAXW], g[MAXW];
int q[MAXW], head, tail, ans = 0;
int main() {
scanf("%d %d", &n, &m);
for (int i = 1, v, w, c; i <= n; i++) {
scanf("%d %d %d", &v, &w, &c);
if (w == 0) {
ans += v * c;
continue;
}
// 防止出现除以 0 的情况
c = min(c, m / w);
for (int r = 0; r < w; r++) {
// 先枚举余数
head = 1, tail = 0;
// 记得情况队列
for (int j = r; j <= m; j += w) {
// 同余枚举
while (head <= tail && (j - q[head]) / w > c)
head++;
while (head <= tail && g[j] - g[q[tail]] > (j - q[tail]) / w * v)
tail--;
// j 比 q[tail] 更优，则直接出队
// 先把单调队列维护好了再来决策
q[++tail] = j;
f[j] = g[q[head]] + (j - q[head]) / w * v;
}
}
memcpy(g, f, sizeof(g));
}
int ans = 0;
for (int i = 1; i <= m; i++)
ans = max(ans, f[i]);
printf("%d\n", ans);
return 0;
}
```
## 完全背包
把 01 背包中$j$的枚举顺序由倒序改为顺序即可。
处理多重背包型方案数问题的时候，用二进制拆分可能会非常困难。此时可以用上完全背包，每次转移后减去不合法的方案数。
## 分组背包
分组背包的 **枚举顺序** 极其重要，枚举顺序为：组数$\rightarrow$体积$\rightarrow$物品。
体积的枚举放在物品前的原因：每个组内只能选一个物品。
可以这样记忆：对于每个组都做一次单个物品的 01 背包，那么就可以保证每个组仅选择一个物品。
```cpp
for (int k = 1; k <= tot; k++)
for (int i = m; i; i--)
for (int j = 1; j <= c[k]; j++)
if (i >= w[k][j])
f[i] = max(f[i], f[i - w[k][j]] + v[k][j]);
```
## 树形背包
树形背包的转移方程和 01 背包是类似的。设$f[u][j]$表示以$u$为根的子树容积为$j$时的最大价值，则可得：
$$f[u][j]=\max_{k=0}^{j}\{f[u][j-k]+f[v][k]\}$$
与背包相同，此处的$j$的枚举顺序也是倒序的。
```cpp
// https://www.luogu.org/problem/P2014
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 10;
struct sidetable {
int to, next;
} edge[MAXN];
int head[MAXN], id = 0;
int n, m, a[MAXN], f[MAXN][MAXN];
void build_edge(int u, int v) {
edge[++id].to = v;
edge[id].next = head[u];
head[u] = id;
return ;
}
void dfs(int u) {
f[u][1] = a[u];
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
dfs(v);
for (int j = m; j; j--)
for (int k = 1; k < j; k++)
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
return ;
}
int main() {
scanf("%d %d", &n, &m);
m++;
// 0 号点是怎么都要选的
for (int i = 1, pre; i <= n; i++) {
scanf("%d %d", &pre, &a[i]);
build_edge(pre, i);
}
dfs(0);
printf("%d", f[0][m]);
return 0;
}
```
### 一个改进
可以看出上面的算法复杂度达到了$O(n^3)$级别，当然是很可能爆掉。可以发现第二、三层循环考虑了很多本来不需要考虑到的情况，因此可以用子树的 `size[]` 来优化枚举。在这种情况下，一个点对$(u,v)$共同出现在转移中的条件是更新到它们的 LCA，因此任意点对都只会出现一次，总复杂度即$O(n^2)$。这也是对冗余转移的优化。
```cpp
void dfs(int u) {
size[u] = 1;
f[u][1] = a[u];
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
dfs(v);
size[u] += size[v];
for (int j = size[u]; j; j--)
for (int k = 1; k <= min(j - 1, size[v]); k++)
// 第二层是 size[u]，第三层是 min(j - 1, size[v])
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
return ;
}
```
## 求方案数
把求最值改为求和即可，注意要把$f[0]$设为$1$。
## 输出方案
可以在 dp 过程中就记录一个$g[i][j]$表示物品$i$在背包容积为$j$的时候是否被选中。因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环；然后按照下面的伪代码执行：
```
int v = V; //记录当前的存储空间
for (从最后一件循环至第一件) {
if (g[i][v]) {
选了第 i 项物品;
v -= 第 i 项物品的价值;
} else {
未选第 i 项物品;
}
}
```
# DAY 2
## 树形 dp
### 树上路径问题
一般这种问题会用到点分治，~~然而我没有学点分治~~，因此只能用树形 dp 去解决。
例题：一棵树，1 号点为根，树上每个节点对应一个值$k[i]$。初始的时候所有点都是白色的。每次操作选择一个节点$i$，$i$必须是白色的，然后$i$到根的链上（包括节点i与根）所有与节点$i$距离小于$k[i]$的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。
分析：维护$f[u][0/1]$，其中$f[u][0]$表示$u$子树中的上次覆盖最远还能覆盖多少个点（不选），$f[u][1]$表示从$u$子树中上次覆盖开始再覆盖一个点最远能够覆盖多少个点（选）。
```cpp
// https://ac.nowcoder.com/acm/problem/13249
void dfs(int u) {
f[u][1] = k[u], f[u][0] = 0;
for (unsigned int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
dfs(v);
f[u][0] = max(f[u][0], f[v][0] - 1);
f[u][1] = max(f[u][1], f[v][1] - 1);
}
if (!f[u][0]) {
// 无法覆盖到此处，必须重新开始覆盖
ans++;
f[u][0] = f[u][1];
f[u][1] = 0;
// u 的父亲不能继承 f[u][1] 的状态
}
return;
}
```
### 树上点对距离和问题
若给一棵树，询问所有点对$(u,v)$中$u\rightarrow v$的路径长度之和，很容易想到的做法是双重 `for` 循环枚举点对，然后用 LCA 计算点对距离。但是这种做法的复杂度是$O(n^2logn)$，即使用 RMQ 实现$O(1)$的 LCA 也是$O(n^2)$，当然是不够优秀的。
考虑用另一种思路处理这个问题：对于每一条边，只需要统计这条边的边权对于答案的贡献。设这条边连接的两点分别为$u,v$（且满足 `dep[u] < dep[v]`），则这条边计入答案的次数就是 $u$及其以上部分子树大小 乘上 $v$的子树大小（乘法原理）。这样的复杂度为$O(n)$，足够优秀。
变形： 设一棵树的所有点都是白色，从中选$k$个节点染成黑色，问黑点的两两距离之和 与 白点的两两距离之和 的和的最大值。
分析：用$f[i][j]$来表示$i$的子树中选$j$个点染成黑点能够对答案产生的最大贡献。用这种方式描述状态以后，就把问题转化为了 **树上满背包** 问题，当然写法和普通的满背包没什么区别。在统计贡献的时候，就可以用到上面提到的乘法原理结论了。
```cpp
void dfs(int u, int fa) {
size[u] = 1;
for (int e = head[u]; e; e = edge[e].next) {
int v = edge[e].to;
if (v == fa)
continue;
dfs(v, u);
size[u] += size[v];
}
memset(f[u], -1, sizeof(f[u]));
f[u][0] = f[u][1] = 0;
for (int e = head[u]; e; e = edge[e].next) {
int v = edge[e].to;
ll w = edge[e].w;
if (v == fa)
continue;
for (int i = min(k, size[u]); ~i; i--)
for (int j = 0; j <= min(i, size[v]); j++)
if (~f[u][i - j]) {
ll ctrb = 1LL * j * (k - j) * w +
1LL * (size[v] - j) * (n - k - size[v] + j) * w;
// 计算当前边的贡献
f[u][i] = max(f[u][i], f[u][i - j] + f[v][j] + ctrb);
}
// 子树大小优化后的满背包
}
return ;
}
```
### 树上最大独立集
例题：选出一些点使得任意两点互不相连（也就是最大独立集）。这个的做法并没有想的那么复杂，用$f[i][0/1]$表示$i$节点 不选 / 选 时以$i$为根的子树的最大独立集，然后感性转移即可。
```cpp
void dfs(int u, int fa) {
f[u][1] = 1;
for (unsigned int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == fa)
continue;
dfs(v, u);
f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}
return ;
}
```
还有些树形 dp 的状态比较多，在状态数组后面多加几个维度就可以了。
## 状态压缩
例题：给出$n$个点，$m$条边，以及$R$个要到达的目的地（保证$n\leq200,R\leq15$），求经过所有目的地的最短路径长度。
分析：这道题难在状态描述。可以先用 Floyd 跑出所有最短路。首先很容易想到用$f[i]$压缩表示目的地是否走过，然后就不知道该怎么转移了。这时可以在状态中添加一个维度变成$f[i][j]$，表示目的地是否走过的情况为$i$，而最后到达$j$点时的最小路径长度。这样做以后，只需要枚举状态$\rightarrow$枚举当前起点$\rightarrow$枚举当前终点，然后进行转移。
```cpp
// https://ac.nowcoder.com/acm/problem/16122
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210;
const int MAXR = 16;
int n, m, R, dst[MAXR];
int dis[MAXN][MAXN];
int f[1 << MAXR][MAXR];
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
return ;
}
int main() {
memset(dis, 0x3f, sizeof(dis));
memset(f, 0x3f, sizeof(f));
scanf("%d %d %d", &n, &m, &R);
for (int i = 1; i <= R; i++)
scanf("%d", &dst[i]);
for (int i = 1; i <= n; i++)
dis[i][i] = 0;
for (int i = 1, a, b, c; i <= m; i++) {
scanf("%d %d %d", &a, &b, &c);
dis[a][b] = dis[b][a] = min(dis[a][b], c);
}
floyd();
for (int i = 1; i <= R; i++)
f[1 << (i - 1)][i] = 0;
for (int i = 1; i < (1 << R); i++)
for (int j = 1; j <= R; j++)
if (i & (1 << (j - 1)))
for (int k = 1; k <= R; k++)
if (!(i & (1 << (k - 1))))
f[i | (1 << (k - 1))][k] = min(
f[i | (1 << (k - 1))][k],
f[i][j] + dis[dst[j]][dst[k]]
);
int ans = 0x3f3f3f3f;
for (int i = 1; i <= R; i++)
ans = min(ans, f[(1 << R) - 1][i]);
printf("%d", ans);
return 0;
}
```
# DAY 3
## 区间 dp
用$f[i][j]$表示$[i,j]$区间的情况。为了保证前驱状态已经获知，一般的枚举顺序为：区间长度$\rightarrow$区间起点$\rightarrow$计算得出区间终点。类似这样：
```cpp
// https://www.luogu.org/problem/P1063
for (int len = 2; len <= n; len++)
for (int i = 1; i <= (n << 1); i++) {
int j = i + len - 1;
for (int k = i; k < j; k++)
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + calc(i, j, k));
}
```
当然也可以附加一维变成$f[i][j][0/1]$，表示考虑$[i,j]$区间，并且处于左端点 / 右端点的情况。
## 前缀和优化
观察：
$$f[i][j]=\sum_{k}^{s[j]-s[k-1]\leq lim}f[k][j-1]$$
这个式子非常吓人，不过可以考虑分步优化。首先把$j$滚动掉，然后考虑使用前缀和优化这个式子：计$s[i][j]=\sum f[i][j]$，那么只要获知表达式中$k$的起始点（可以预处理），就可以$O(1)$地计算出$f[i][j]$的值，同时动态维护下一次要调用到的前缀和。
```cpp
// https://www.luogu.org/problem/P2511
int cur = 0;
for (int i = 1; i <= n; i++) {
while (s[i] - s[cur] > lim)
cur++;
L[i] = cur;
}
// 隔板法，有些写法没有见过
for (int i = 0; i <= n; i++)
sum[i][0] = 1;
for (int J = 1, j = 1; J <= m; J++, j ^= 1) {
sum[0][j] = 0;
for (int i = 1; i <= n; i++) {
f[i][j] = sum[i - 1][j ^ 1] % mod;
if (L[i] - 1 >= 0)
f[i][j] = (f[i][j] - sum[L[i] - 1][j ^ 1] + mod) % mod;
sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
}
ans = (ans + f[n][j]) % mod;
}
```
## 最长单调子序列
一般是用贪心去做，即维护一个数组$b[i]$，其末尾表示当前长度的最长单调子序列的末尾最大 / 最小是多少。每次得到一个数$a[i]$，要么合法地接在$b$数组的末尾；要么二分查找$b$中的某个符合条件的值（用 `upper_bound()` 或者 `lower_bound()` 都有可能），然后把它替换掉。
当然还有树状数组写法。离散化以后，用$f[i]$表示以$i$结尾的最长单调子序列长度，考虑最朴素的转移方程：
$$f[i]=\max^{j<i}\{f[j]\}+1$$
其中$\max\{f[j]\}$就可以用树状数组维护。
两种方法都是$O(nlogn)$的复杂度。
# DAY 4
对于一类需要优化的题目，写出状态转移方程以后，观察式子有没有关于$i,j$的交叉项；有交叉项就使用斜率优化，没有交叉项就使用单调队列优化。
还有一种方法是假设一个决策比另一个决策优，推出单调队列需要维护的东西，然后再进行优化。
## 斜率优化
斜率优化的使用前提是：能够把状态转移方程写成形如$b=y+k\cdot x$的形式，其中$b,k$只与$i$有关，而$x,y$只与$j$有关。得出式子以后，要想清楚单调队列究竟是维护上凸还是下凸；同时还要注意计算直线斜率的时候会不会遇到除以$0$的情况（验斜不在）。
例题：把$n$个数分成$k$个集合，每次分割获得的分数是所分得的两个集合 各自总和 之积。求最大得分并输出方案。
分析：首先，设三个数为$a,b,c$，则无论怎么分割，最后的得分都是$ab+ac+bc$，这为使用斜率优化以及记录路径降低了难度。用$s[i]$表示前缀和，$f[i][j]$表示前$i$个数分成$j$段的最大得分，则有朴素转移方程：
$$f[i][j]=\max\{f[k][j-1]+s[k]\cdot(s[i]-s[k])\}$$
滚动掉$j$的维度，设$g[i]=f[i][j-1]$，则：
$$f[i]=\max\{g[j]+s[i]\cdot s[j]-s^2[j]\}$$
忽略掉$\max$，原式整理为：
$$s^2[j]-g[j]=s[i]\cdot s[j]-f[i]$$
也就是$l:y=kx-b$的形式。这里是要求$b$的最大值，也就是让$l$最低，所以维护下凸即可。需要注意的是，**调用函数会降低性能**，所以不要写一堆 `x(i)` 和 `y(i)` 什么的再来算 `slope(i, j)`。
关于记录路径，用 `pre[i][j]` 表示 `f[i][j]` 由 `f[pre[i][j]][j-1]` 转移而来，最后从 `f[n][k]` 开始倒序遍历。
```cpp
// https://www.luogu.org/problem/P3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
const int MAXK = 210;
int n, k, a[MAXN];
ll s[MAXN], f[MAXN][2];
int q[MAXN], head, tail, pre[MAXN][MAXK];
double slope(int a, int b, int j) {
if (s[a] == s[b])
return 1e18;
// 注意验斜不在
return 1.0 * (s[a] * s[a] - f[a][j] - s[b] * s[b] + f[b][j]) / (s[a] - s[b]);
}
int main() {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
for (int J = 1, j = 1; J <= k; J++, j ^= 1) {
head = tail = 0;
q[head] = 0;
for (int i = 1; i <= n; i++) {
while (head < tail && slope(q[head], q[head + 1], j ^ 1) < s[i])
head++;
while (head < tail && slope(i, q[tail], j ^ 1) < slope(i, q[tail - 1], j ^ 1))
tail--;
f[i][j] = s[q[head]] * (s[i] - s[q[head]]) + f[q[head]][j ^ 1];
pre[i][J] = q[head];
// 记录路径
q[++tail] = i;
}
}
printf("%lld\n", f[n][k & 1]);
for (int x = n, i = k; i; i--)
x = pre[x][i], printf("%d ", x);
return 0;
}
```
注意一点：斜率优化中，由于斜率的计算需要用到$f[i]$的值，所以应该要先计算$f[i]$，再把$i$扔进单调队列中，否则斜率的计算就会出问题。
### 费用提前
如果发现$f[i][j]$需要滚动才能使用斜率优化，并且式子中出现了与$j$有关的项阻碍对式子的整理，那么就可以把与$j$的项通过后缀思想转化为与$j$无关的项。
例题：任务完成（费用$=$完成时刻$\times$费用系数）
分析：用$f[i][j]$表示前$i$个任务分成$j$次完成的最小用时，朴素的转移方程为：
$$f[i][j]=\min\{f[k][j-1]+(j\cdot S+st[i])\cdot(sf[i]-sf[k])\}$$
然后考虑在一个点多启动一次机器，则会使费用增加$S\times\sum$后面的费用系数。因此把这个费用提前到该点计算，可得：
$$f[i][j]=\min\{f[k][j-1]+st[i]\cdot(sf[i]-sf[k])+S\cdot(sf[n]-sf[k])\}$$
再考虑把$j$滚动掉，就可以进行斜率优化了。
# DAY 5
## 路径压缩
以前的笔记：[路径压缩](https://ncc79601.blog.luogu.org/shorten-path-dp)
也就是特殊的离散化，多半是用 LCM 来压路径。
需要注意的是，路径压缩只是把稀疏路径压缩成稠密路径，也就是说开空间还是要开到 `MAXN * LCM` 级别。
## 齐线法
齐线法有些搞忘了，甚至于该怎么写都有点懵。本质上来说，齐线法也是一个动态规划的过程，只是其状态由多个变量组成。
转移的时候，若上一行符合题意，则上一行的状态继承到当前行。为了保证取得的部分是合法的矩形，所以有些取 `max()` 和 `min()` 的操作。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2080;
int n, m, a[MAXN][MAXN];
int l[MAXN][MAXN], r[MAXN][MAXN], h[MAXN][MAXN];
int ans1 = 0, ans2 = 0;
// ans1 - 正方形， ans2 - 长方形
inline int sq(int x) { return x * x; }
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
l[i][j] = r[i][j] = j;
h[i][j] = 1;
}
for (int i = 1; i <= n; i++)
for (int j = 2; j <= m; j++)
if (a[i][j] != a[i][j - 1])
l[i][j] = l[i][j - 1];
for (int i = 1; i <= n; i++)
for (int j = m - 1; j; j--)
if (a[i][j] != a[i][j + 1])
r[i][j] = r[i][j + 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (i > 1 && a[i][j] != a[i - 1][j]) {
l[i][j] = max(l[i][j], l[i - 1][j]);
r[i][j] = min(r[i][j], r[i - 1][j]);
h[i][j] = h[i - 1][j] + 1;
}
ans1 = max(ans1, sq(min(r[i][j] - l[i][j] + 1, h[i][j])));
ans2 = max(ans2, (r[i][j] - l[i][j] + 1) * h[i][j]);
}
printf("%d\n%d", ans1, ans2);
return 0;
}
```
# DAY 6
只剩下最后一周了。
真的很累，很累。
所承受的一切，不知该向谁倾诉。
**只是期盼着，暗夜中能再闪耀一粒星辰；**
**只是等待着，绝望中能再瞥见一缕亮光。**
$\text{I tend to lose my sense of time and come the morning,}$
$\large\text{Stayed aside.}$
$\text{I know it's much too soon to tell you that I need you,}$
$\large\text{By my side.}$
$\text{But who are we to call each other selfish lovers?}$
$\Large\text{We all need someone to} \huge\text{ hold.}$
$\footnotesize\texttt{Hold feat. Daniela Andrade}$