收錄一些比較冷門的 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\)，需要用這個資訊轉移到它更後面的位置。
注意這裡 \(\to\) 符號表示將箭頭前的揹包按點值合併到箭頭指向的揹包，複雜度是 \(\mathcal{O}(V)\) 而非 \(\mathcal{O}(V ^ 2)\)。
不難發現我們在 \(\mathcal{O}(nV)\) 的時間內解決了簡化後的問題。對於原問題而言，注意到我們選擇作為根的節點時必然被選擇的，所以任何一個包含根節點的方案均在本次 DP 中被考慮到。根節點裂開後整棵樹形成若干連通塊，這讓我們聯想到點分治。因此，用點分治優化上述 DP，這使得我們不用以每個節點作為根 DP 整棵樹。時間複雜度 \(\mathcal{O}(n\log n V)\)。
給出程式碼。
#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 -> id
f[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;
}
問題相當於選擇從根到某個點的路徑，免費選一個蘋果，再做樹上依賴性揹包。這個點肯定是葉子，因為多選免費蘋果一定更優。
設 \(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\) 個蘋果，回溯時再強制加入最後一個蘋果。
單調佇列優化多重揹包，時間複雜度 \(\mathcal{O}(nk)\)，程式碼。
設 \(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 陣列的做法更簡潔。程式碼 和題解略有不同。