设 \(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)\)，代码 。
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} = \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 数组的做法更简洁 。代码 和题解略有不同 。
【DP 优化小技巧】
推荐阅读
- 自定义View6 -塔防小游戏：第三篇防御塔随意放置+多组野怪
- 起点小说盟主多少钱|起点小说网上的盟主是什么意思？
- Spring让人眼前一亮的11个小技巧
- 小米手环6丢失如何找回_小米手环6支持定位找回吗
- 小孩的飞棋是怎么玩的（小孩玩的飞行棋的玩法)
- 华为nova9和小米11青春版哪个好_哪款更值得入手
- 小米11Lite和小米11有什么区别_小米11Lite和小米11参数对比
- 军棋的正确玩法和技巧有哪些（军棋的正确摆放图)
- 小米11pro评测_小米11pro全面评测
- redmi watch和小米手表color哪款更值得买?