DP 优化小技巧 _生活百科

收录一些比较冷门的 DP 优化方法。
1. 树上依赖性背包树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于 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)\) 。
I. P6326 Shopping给出代码。

#include <bits/stdc++.h>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 <int> e[N];struct Knapsack {	int a[M];	void clear() {memset(a, 0, M << 2);}	void merge(Knapsack rhs) {for(int i = 0; i <= m; i++) a[i] = max(a[i], rhs.a[i]);}	void insert(int c, int w, int v) {static int d[M], f[M], hd, tl;memset(f, 0xcf, M << 2);for(int i = 0; i < w; i++) {d[hd = tl = 1] = i;for(int j = i + w; j <= m; j += w) {while(hd <= tl && d[hd] + c * w < j) hd++;f[j] = a[d[hd]] + (j - d[hd]) / w * v;while(hd <= tl && a[j] - j / w * v >= 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 -> idf[i].merge(tmp);	}	for(int i = 0; i <= m; i++) ans = max(ans, f[1].a[i]);	for(int it : e[id]) if(!vis[it]) R = 0, findroot(it, id, sz[it]), divide(R);}void solve() {	cin >> n >> m;	memset(vis, 0, sizeof(vis)), ans = 0; // ADD THIS LINE!!!!!	for(int i = 1; i <= n; i++) e[i].clear();	for(int i = 1; i <= n; i++) cin >> w[i];	for(int i = 1; i <= n; i++) cin >> c[i];	for(int i = 1; i <= n; i++) cin >> 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;}

*II. P3780 [SDOI2017] 苹果树问题相当于选择从根到某个点的路径，免费选一个苹果，再做树上依赖性背包。这个点肯定是叶子，因为多选免费苹果一定更优。