收录一些比较冷门的 DP 优化方法。
树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于 01 背包，多重背包和完全背包均可以在 (\mathcal{O}(V)) 的时间内加入一个物品，(\mathcal{O}(V ^ 2)) 的时间内合并两个背包，所以不妨设背包类型为多重背包。
先考虑一个弱化版问题。给定一棵有根树，若一个节点被选，则它的父亲必须被选。
显然存在一个 (\mathcal{O}(nV ^ 2)) 的树形 DP 做法，它能求出以每个节点为根时其子树的答案。
接下来引出科技： 树上依赖性背包。我们发现对每个节点都求答案似乎有些累赘，因为我们只关心以 (1) 为根时的答案。对做法的形象描述为：让背包从根节点的地方出发，对于每个节点 (i)，如果不选，那么跳过 (i) 的整棵子树，否则强制选该节点上的物品至少一件，并将这个背包带到子树里逛一圈（因为父亲节点选了）。注意到两种选择实际上是并列的，所以合并背包是合并它们的 点值，即对应位置取 (\max)。
让我们用更严谨的语言描述上述过程。不妨设节点已经按照它们的 dfs 序排好序了，节点 (i) 的子树大小为 (sz)。
设 (f_i) 表示前 (i – 1) 个节点在限制下的答案（ 是一个背包），对于当前节点 (i) 而言，我们已知 (f_i)，需要用这个信息转移到它更后面的位置。
- 如果节点(i) 被选择，那么只需它的儿子子树满足限制。换言之，选择节点(i) 之后，它们的儿子可以选择选或者不选，这个选择的自由留给子节点决策，所以只有节点(i) 是否被选择的信息固定了下来的。因此(f_i + K_i \to f_{i + 1})。这里(+K_i) 表示将物品(K_i) 加入背包(f_i)。
- 如果节点(i) 不被选择，那么它的整棵子树也不能选。所以它的整棵子树的状态就确定了下来：均不选。因此(f_i \to f_{i + sz_i})。
注意这里 (\to) 符号表示将箭头前的背包按点值合并到箭头指向的背包，复杂度是 (\mathcal{O}(V)) 而非 (\mathcal{O}(V ^ 2))。
不难发现我们在 (\mathcal{O}(nV)) 的时间内解决了简化后的问题。对于原问题而言，注意到我们选择作为根的节点时必然被选择的，所以任何一个包含根节点的方案均在本次 DP 中被考虑到。根节点裂开后整棵树形成若干连通块，这让我们联想到点分治。因此，用点分治优化上述 DP，这使得我们不用以每个节点作为根 DP 整棵树。时间复杂度 (\mathcal{O}(n\log n V))。
给出代码。
#include
using namespace std;
const int N = 500 + 5;
const int M = 4e3 + 5;
int n, m, ans;
int w[N], c[N], d[N];
vector e[N];
struct Knapsack {
int a[M];
void clear() {memset(a, 0, M << 2);}
void merge(Knapsack rhs) {for(int i = 0; i = a[d[tl]] - d[tl] / w * v) tl--;
d[++tl] = j; // ADD THIS LINE
}
}
memcpy(a, f, sizeof(a));
}
} f[N];
int vis[N], mx[N], sz[N], R;
void findroot(int id, int fa, int tot) {
sz[id] = 1, mx[id] = 0;
for(int it : e[id])
if(!vis[it] && it != fa) {
findroot(it, id, tot);
sz[id] += sz[it], mx[id] = max(mx[id], sz[it]);
}
mx[id] = max(mx[id], tot - sz[id]);
if(mx[id] < mx[R]) R = id;
}
int dn, dfn[N], rev[N];
void dfs(int id, int fa) {
rev[dfn[id] = ++dn] = id, sz[id] = 1;
for(int it : e[id]) if(!vis[it] && it != fa) dfs(it, id), sz[id] += sz[it]; // ADD sz[id] += sz[it]
}
void divide(int id) {
vis[id] = 1, dn = 0, dfs(id, 0);
f[dn + 1].clear(); // e -> f
for(int i = dn; i; i--) {
int id = rev[i];
f[i] = f[i + sz[id]];
Knapsack tmp = f[i + 1];
tmp.insert(d[id], c[id], w[id]); // i -> id
f[i].merge(tmp);
}
for(int i = 0; i > n >> m;
memset(vis, 0, sizeof(vis)), ans = 0; // ADD THIS LINE!!!!!
for(int i = 1; i > w[i];
for(int i = 1; i > c[i];
for(int i = 1; i > d[i];
for(int i = 1, u, v; i < n; i++) cin >> u >> v, e[u].push_back(v), e[v].push_back(u);
R = 0, findroot(1, 0, n), divide(R);
cout << ans << endl;
}
int main() {
mx[0] = N;
int T;
cin >> T;
while(T--) solve();
return 0;
}
问题相当于选择从根到某个点的路径，免费选一个苹果，再做树上依赖性背包。这个点肯定是叶子，因为多选免费苹果一定更优。
设 (f) 表示当前可以继续往下延伸免费苹果的背包数组，(g) 表示不可以再向下延伸免费苹果的背包数组，则对于 (u) 及其子节点 (v)，(f_u \otimes f_v\to g_u)，(f_u\otimes g_v\to g_u)，(g_u\otimes g_v \to g_u)。很遗憾，如果用树上依赖性背包，我们会发现上面三种转移无法合并，必须向下递归三个子问题。也就是说，每层将凭空多出来一个背包数组。这个方法行不通。
换种角度，想象一棵树，每个儿子按访问顺序从左到右排列，则从根到叶子的路径将整棵树劈成两半，左边和右边时间戳分别连续。对于中间有特殊部分的问题，套路地维护前后缀再合并。又因为树上依赖背包可以算出每个时间戳前缀的答案，所以可行。
因此，设 (f_i) 表示考虑到时间戳前缀 (i) 的答案，满足时间戳为 (i) 的节点 (rev_i) 到根的路径上所有节点还没有被加入背包。(g_i) 同理表示后缀。求出 (f, g) 后枚举每个节点 (i)，则相当于合并 (f_{dfn_i})，(g_{dfn_i}) 和 (i) 到根上所有节点 (j) 在 (a_j) 减掉 (1) 之后的背包 (h_i)，得到一个大背包 (K)，则 (K_k) 加上 (i) 到根上所有节点的 (v) 之和的最大值即为答案。
这样还是不太行，因为 (K_k) 需要 (k ^ 2) 的时间。考虑将 (h) 巧妙地融合到 (f) 或 (g) 当中，发现设 (f_i) 满足 (rev_i) 到根的路径上所有节点 (j) 暂时只考虑了 (a_j – 1) 个苹果，且这 (a_j – 1) 个苹果不强制至少选一个，即可满足条件。也就是说，进入 (j) 时只不强制必须选地加入 (a_j – 1) 个苹果，回溯时再强制加入最后一个苹果。
设 (f_{i, j, k, l}) 表示以 ((i, j)) 为左上角，((k, l)) 为右下角的矩形的混乱度，直接做时空复杂度至少 (n ^ 4)，无法接受。
因为每次在矩形中间切一刀使得矩形大小减半，混乱度加 (1)，所以答案为 (\log) 级别。进一步地，固定左边界 (j)，上边界 (i) 和下边界 (k)，当 (l) 向右移动时，混乱度不降。显然，若矩形 (A) 包含矩形 (B)，则 (A) 的混乱度不小于 (B) 的混乱度。根据这个单调性，设 (f_{i, j, k, a}) 表示使得混乱度不大于 (a) 的最大的 (l)。(a) 这一维只有 (\log)，且可以滚动数组优化掉。
初始化 (f_{i, j, k} = l) 当且仅当对应矩形字符全部相等，且 (l + 1) 对应矩形字符不全相等。枚举 (i, j)，随着 (k) 递增 (l) 不降，可以 (n ^ 3) 预处理。
考虑横着切。枚举左边界 (j)，上边界 (i)，下边界 (k)。若再枚举切割位置 (p)，则复杂度 (n ^ 4)。但我们注意到转移形如 (f_{i, j, k} = \max\limits_{p = i} ^ {k – 1} \min(f_{i, j, p}, f_{p + 1, j, k}))，因为 (f_{i, j, p}) 在固定 (i, j) 时关于 (p) 单调，(f_{p + 1, j, k}) 在固定 (j, k) 时关于 (p) 单调，在固定 (p, j) 时关于 (k) 单调，所以当 (k) 递增时，决策点 (p) 单调不降。反证法结合单调性容易证明。因此不需要二分决策点，用指针维护即可。
竖着切就太简单了，枚举 (i, j, k)，则 (f_{i, f_{i, j, k} + 1, k}) 贡献到新的 (f_{i, j, k})。
时间复杂度 (\mathcal{O}(n ^ 3\log n))，比题解区 (n ^ 3\log ^ 2 n) 的做法时间复杂度更优，(n ^ 3\log n) 但需要两个 DP 数组的做法更简洁。代码 和题解略有不同。
Original: https://www.cnblogs.com/alex-wei/p/dp_tricks.html
Author: qAlex_Weiq
Title: DP 优化小技巧
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/801429/
转载文章受原作者版权保护。转载请注明原作者出处！