DP 优化小技巧

2022-10-05

收录一些比较冷门的 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}(nlog n V))。

I. P6326 Shopping

给出代码。

#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 = 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]  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 > u >> v, e[u].push_back(v), e[v].push_back(u);
    R = 0, findroot(1, 0, n), divide(R);
    cout > T;
    while(T--) solve();
    return 0;
}

*II. P3780 [SDOI2017] 苹果树

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

设 (f) 表示当前可以继续往下延伸免费苹果的背包数组，(g) 表示不可以再向下延伸免费苹果的背包数组，则对于 (u) 及其子节点 (v)，(f_u otimes f_vto g_u)，(f_uotimes g_vto g_u)，(g_uotimes 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))，代码。

2. 值域定义域互换

*I. AT4927 [AGC033D] Complexity

设 (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} = maxlimits_{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 ^ 3log n))，比题解区 (n ^ 3log ^ 2 n) 的做法时间复杂度更优，(n ^ 3log n) 但需要两个 DP 数组的做法更简洁。代码和题解略有不同。

文章来源于互联网：DP 优化小技巧

THE END

二维码