「赛前备战」NOIp2020-提高 动态规划训练

博主太菜,可能会炸联赛,于是恶补一下 QAQ

动态更新

「eJOI2017」Experience

update - 2020.7.27

树形 dp

设 \(f(x, 0), f(x, 1)\) 分别表示以 \(x\) 为根的子树,\(x\) 所在链为向下(非严格)递减、递增时的答案。

题目中要求求极差,那么结点 \(x\) 可能为最大值或最小值。

以向下递减为例,我们在所以满足 \(W_x \ge W_y\) 的所有子结点 \(y\) 中,将原本 \(y\) 的贡献用 \(x\) 作为新的最大值替换,并更新 \(f(x, 0)\) 的答案。向下递增也是同理,不过这里是作为最小值,因此符号会改变。

在做结点 \(x\) 是,我们设 \(p = \sum\limits_{y \in \text{son}(x)} \max(f(y, 0), f(y, 1))\),并令 \(p\) 为 \(f(x, 0), f(x, 1)\) 的初始值。

那么状态转移方程(\(\leftarrow\) 表示最(大)值操作):

\[f(x, 0) \leftarrow \max\limits_{y\in \text{son}(x), W_x \ge W_y}\{p - \max(f(y, 0), f(y, 1)) + W_x - W_y\}\\ f(x, 1) \leftarrow \max\limits_{y\in \text{son}(x), W_x \le W_y}\{p - \max(f(y, 0), f(y, 1)) - W_x + W_y\} \]

时间复杂度 \(O(n)\)。

「eJOI2018」山

update - 2020.7.27

设 \(f(n, k, 0), f(n, k, 1), f(n, k, 2)\) 表示 \([1, n]\) 中,建造了 \(k\) 座房子,且第 \(n-1\),第 \(n\) 个位置的状态分别为 \((0,0),(1, 0), (0, 1)\) 时(\(0\) 表示没有房子,\(1\) 表示有)的最小花费时间。

状态转移方程:

\[f(n, k, 0) = \min\{f(n-1, k, 0), f(n-1, k, 1)\} \\ f(n, k, 1) = f(n-1, k, 2) + \text{get}(a_n - a_{n - 1} + 1)\\ f(n, k, 2) = \min\{f(n-1, k-1, 0) + \text{get}(a_{n-1} - a_n + 1), f(n-1, k-1,1)+\text{get}(\min(a_{n-2}-1, a_{n-1})-a_{i}+1)\}\\ \text{其中 } \text{get}(x)=\max(x, 0) \]

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

「CSP2019-J」纪念品

update - 2020.7.27

背包 dp

直接存物品的个数显然原地升天。但仔细想一下发现,转换成统一在第 \(i\) 天买,然后在第 \(i+1\) 天卖,其实等价。因为即使对某种物品实际上并不操作,换成全卖了然后买回来也未尝不可。

不难设计出一个比较暴力的状态:\(f(i, j, k)\) 表示第 \(i\) 天,对于前 \(j\) 个物品,剩余现金为 \(k\) 时,下一天手头上的最大现金数。转移方程显然。

为了不空间爆炸,我们尝试优化。第一维显然可以缩掉——我们只要上一轮的最优值即可。剩下了两维看着像一个背包,于是倒序以下就只剩最后一维了。方程:

\[f(k) \leftarrow \max(f(k), f(k - P_{i, k})+P_{i, k+1}-P_{i, k}) \]

时间复杂度 \(O(TN\times \max P)\)。

上一篇:thusc2021题解


下一篇:「JSOI2014」打兔子