1. 首頁 > 生活百科 > >

DP 優化小技巧

生活百科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] 蘋果樹問題相當于選擇從根到某個點的路徑 ， 免費選一個蘋果，再做樹上依賴性背包 。這個點肯定是葉子，因為多選免費蘋果一定更優 。

推薦閱讀