[土豆编程杯 2024 初赛] 采矿

Kevin090228 · 2024-01-08 21:20:17 · 题解

通过对题目背景的阅读得知只有一个机器人。所以 DP 状态设计是显然的：f(i,j,l,r) 表示考虑了前 i 次操作，机器人在点 j，j 的左右子树内分别有 l,r 个人类的最大产出。

对于操作 3,4，转移是简单的，直接 f(i,j,l,r)\to f(i+1,j,l,r) 即可。

这里设辅助数组 g(u,l,r) 表示在机器人移动中，在 u 点，左右子树有 l,r 个的最大产出。要注意机器人必须移动，所以 g 的初值也要转移得到，而不能直接复制。

对于操作 1，由深到浅进行树形 DP。不妨设 u 是 f_u 左儿子，有转移：g(u,a,b)\to g(f_u,a+b,c)，对于每个 a+b 求出 g(u,a,b) 最大值，然后就能枚举 c 转移了，时间复杂度是树形背包的 O(n^2)。

对于操作 2，由浅到深进行树形 DP。不妨设 u 是 f_u 左儿子，有转移：g(f_u,a,b)\to g(u,c,a-c)，类似地，对于每个 a 求出 g(f_u,a,b) 最大值，然后就能枚举 c 转移，时间复杂度同样是树形背包的 O(n^2)。

对于计算采矿的贡献，预处理 A(u,c),B(u,c) 分别表示在 u 子树内/外放 c 个人的最大采矿产出即可。

总时间复杂度 O(n^2c)。