dp 题目选做

# UVA1292 Strategic game

树形 $\text{dp}$ 板子题。

直接设 $f_{x, 0/1}$ 表示 $x$ 子树内所有的边都被看守到，且 $x$ 不放 或者 放 士兵的最少士兵数。

• $x$ 如果不放士兵，它的所有儿子节点都必须放士兵，即：

  $$dp_{x, 0} += dp_{y, 1}$$

• $x$ 如果放士兵，那么它的儿子可放可不放，即：

  $$dp_{x, 1} += \min\{dp_{y, 0}, dp_{y, 1} \}$$

# P7690 [CEOI2002] A decorative fence

非常神仙的 $\text{dp}$，不理解为什么只是绿牌题。

这题看到之后毫无思路 QwQ，可能是我太菜了于是看了一眼题解。

我们设 $dp_{i, j, 0/1}$ 表示从左到右放了 $i$ 块木板，最左边的一块是第 $j$ 低的，且 0 表示最左边的木板低于它右边的那个，1 反之时的方案数。

不难得到转移方程：

$$dp_{i, j, 0} = \sum_{k = j}^{i - 1} dp_{i - 1, k, 1} \\ dp_{i, j, 1} = \sum_{k = 1}^{j - 1}dp_{i - 1, k, 0}$$

就是把当前最左边的一位删掉之后可能的状态。时间复杂度 $O(n^3)$

$\text{dp}$ 之后的输出方案更是困难，但是这里只讲 dp，不是题解，所以不说了。

# SP15637 GNYR04H - Mr Youngs Picture Permutations

观察到最多只有 5 行（我根本观察不到 /kk），直接暴力 5 维 $\text{dp}$。

设 $f_{a, b, c, d, e}$ 表示从上到下每行的人数，由于上面一行人数要大于等于下面一行的人数，所以转移的时候判一下。

举个例子：

$$dp_{a, b + 1, c, d, e} += dp_{a, b, c, d, e} (b < n_2, a > b)$$

# P2893 [USACO08FEB] Making the Grade G

似乎有无数倍经验。

本题有非常妙的贪心做法，这里就不讲了，来说一下如何 $\text{dp}$。

首先需要知道一个结论：

修改后的高度肯定都是输入中出现过的高度。

就不证明了。

那么我们就有一个比较显然的状态，设 $dp_{i, j}$ 表示修改到第 $i$ 条路，修改后的高度是 $h_j$，转移方程：

$$dp_{i, j} = \min\{dp_{i - 1, k} \} + |a_i - h_j|\ \ (1 \leq k \leq j)$$

$a_i$ 是输入的第 $i$ 条路的高度，$h_i$ 是 $a_i$ 排序去重之后的结果。

但是直接转移是 $O(n^3)$ 的，考虑如何优化。

不难发现 $\min\{dp_{i - 1, k} \}$ 这个东西非常多余，我们在转移当前层的时候再开个数组记一下最小值即可。

然后复杂度就变成 $O(n^2)$ 的了。

# SP703 SERVICE - Mobile Service

看到这道题，先不要想太多，大胆设状态，把所有需要存下来的都存下来，于是有一个很暴力的状态，设 $dp_{i, x, y, z}$ 表示处理到了第 $i$ 个询问，三个人分别在 $x, y, z$ 三个位置上时的最小花费。

转移也很暴力：

$$dp[i + 1][p_{i + 1}][y][z] = \min\{dp[i][x][y][z] + w(x, p_{i + 1}) \} \\ dp[i + 1][x][p_{i + 1}][z] = \min\{dp[i][x][y][z] + w(y, p_{i + 1}) \} \\ dp[i + 1][x][y][p_{i + 1}] = \min\{dp[i][x][y][z] + w(z, p_{i + 1}) \} \\$$

但是这样的时空复杂度我们无法接受，即使把第一维滚掉时间上依旧是 $O(n^3m)$ 的。

如何优化呢？

我们观察到题目中时这么说的：

公司必须按照顺序，派一名员工到位置 $x_i$。

这又什么意义呢？相当于是告诉我们了在处理完第 $i$ 个请求时必有一个点在 $p_i$，所以我们只需要记录两个不在请求位置上的点的位置即可。

转移的话和上面几乎是一样的：

• $dp[i + 1][x][y] = \min\{dp[i][x][y] + w(p_i, p_{i + 1}) \}$，第三个人从 $p_i$ 跑到 $p_{i + 1}$。
• $dp[i + 1][x][p_i] = \min\{dp[i][x][y] + w(y, p_{i + 1}) \}$ 第二个人从 $y$ 跑到 $p_{i + 1}$，此时第三个人在上个请求中跑到了 $p_i$，所以把 $p_i$ 存下来。
• $dp[i + 1][p_i][y] = \min\{dp[i][x][y] + w(x, p_{i + 1}) \}$ 同上面。

# P6064 [USACO05JAN]Naptime G

先假设不能构成环，考虑如何 $\text{dp}$。

设 $dp_{i, j, 0/1}$ 表示到了第 $i$ 个时间，已经连着睡了 $j$ 个时间，当前是否睡觉，0 表示不睡，1 表示睡。

那么显然有转移方程：

$$dp_{i, j, 0} = \max\{dp_{i - 1, j, 1}, dp_{i - 1, j, 0} \} \\ dp_{i, j, 1} = \max\{dp_{i - 1, j - 1, 0}, dp_{i - 1, j - 1, 1} + w_i \}$$

但是时间是可以循环的，如何处理呢？

我们强制可以得到时间 1 的效用值即可，也就是强行把 1 和 $n$ 连起来了。

这样为什么可以呢？

考虑如果我们没有得到时间 1 的效用值，那么即使时间可以循环也是无所谓的，所以这要就足够了。

我们只需要在赋初值时令 $dp_{1, 1, 1} = w_1$，且最后统计答案时只对 $dp_{n, b, 1}$ 取较小值即可。

# P2687 [USACO4.3] 逢低吸纳 Buy Low, Buy Lower

$O(n^2)$ 的最长下降子序列就不说了，直接来看方案数如何计算。

其实就是在最长下降子序列的 $dp$ 数组上再跑一个 $\text{dp}$。

一般情况下，如果 $dp_{i} = dp_j + 1$ 且 $a_i < a_j\ \ (i > j)$ 我们令 $f_i += f_j$，但是这样明显会算重很多东西。

（$dp_i$ 为最长下降子序列的数组，$f_i$ 为计算方案数的数组）

考虑如何去重。

如果 $dp_i = dp_j$ 且 $a_i = a_j\ \ (i > j)$ 的话，那这个位置我们会多算，所以直接令 $f_j = 0$ 即可。

# P1081 [NOIP2012 提高组] 开车旅行

倍增优化 $\text{dp}$ 好题。

设三个 $\text{dp}$ 数组:

• $f_{i, j, k}\ \ (k = 0/1)$，表示从 $j$ 出发行驶了 $2^i$ 天，$k$ 先开车，最终到达的城市。
• $da_{i, j, k}$，表示从 $j$ 出发行驶了 $2^i$ 天，$k$ 先开车，小 $\text{A}$ 行驶的路程。
• $db_{i, j, k}$，表示从 $j$ 出发行驶了 $2^i$ 天，$k$ 先开车，小 $\text{B}$ 行驶的路程。

初值为：

$$f_{0, i, 0} = nxt_a, f_{0, i, 1} = nxt_b\\ da_{0, i, 0} = dis(a, nxt_a) \\ db_{0, i, 1} = dis(b, nxt_b)$$

$a$ 为小 $\text{A}$ 当前所在位置，$nxt_a$ 为下一步到达的位置，$b, nxt_b$ 同理。

初值应该比较好理解吧。

再来看转移，转移要分为两种情况，因为 $2^0 = 1$ 是奇数， 会导致开车的人发生变化；其他的 $2^x(x \neq 0)$ 为偶数，开车的人不会变，所以：

• 当 $i = 1$ 时：

  $$f_{1, j, k} = f_{0, f_{0, j, k}, k \oplus 1} \\ da_{1, j, k} = da_{0, j, k} + da_{0, f_{0, j, k}, k \oplus 1} \\ db_{1, j, k} = db_{0, j, k} + db_{0, f_{0, j, k}, k \oplus 1}$$

• 当 $i > 1$ 时：

  $$f_{i, j, k} = f_{i - 1, f_{i - 1, j, k}, k} \\ da_{i, j, k} = da_{i - 1, j, k} + da_{i - 1, f_{i - 1, j, k}, k} \\ db_{i, j, k} = db_{i - 1, j, k} + db_{i - 1, f_{i - 1, j, k}, k}$$

$\text{dp}$ 到这里就结束了，稍微讲一下如何计算答案。

套路倍增查询，设当前在 $s$ 点，还能行驶 $x$ 公里，当前枚举到 $i$，即走 $2^i$ 天。

判断，若走 $2^i$ 天之后还没到终点，且两人行驶的距离加起来没有超过 $x$ 就走 $2^i$ 天。

两种询问都可以通过调用这个查询函数来实现。

# UVA12983 The Battle of Chibi

计算长度为 $m$ 的严格上升子序列个数。

首先设计一个比较暴力的 $\text{dp}$，设 $dp_{i, j}$ 表示考虑到第 $i$ 位，长度位 $j$ 的上升子序列个数。

那么有转移方程：

$$dp_{i, j} = \sum_{k = 1}^{i - 1}[a_k < a_i]dp_{k, j - 1}$$

但是这个转移的复杂度是 $O(n^3)$ 的，无法通过此题，考虑优化。

先不管 $j$ 的一维，不难发现就是求 $i$ 前面小于 $a_i$ 的和，直接整个树状数组优化即可。

现在加上 $j$ 这一维，那就开个二维树状数组。

# UVA1640 统计问题 The Counting Problem

数位 $\text{dp}$ 板子题。

简单说一下吧，对于 $0 \sim 9$ 分开考虑，即每次计算一个数字的出现次数。

数位 $\text{dp}$ 基本思想，先计算 $1 \sim r$ 的答案再减去 $1 \sim l - 1$ 的答案。

假设当前要求 $1 \sim x$ 中 $now\ (now \in [0, 9])$ 的出现次数。

还是 $dfs(pos, cnt, lim, flag)$：

• $pos$：$x$ 十进制下第几位。
• $cnt$：$now$ 出现了多少次。
• $lim$：当前位是否有上限。
• $flag$：前面是否都为前导 0。

里面的 $dfs$ 调用时这么写：

$$dfs(pos - 1, cnt + (!(flag \& (!i)) \& (i == now)), lim \& (i == tmp), flag \& (!i))$$

其中 $!(flag \& (!i))$ 为判断当前位是否是前导 0，因为 $now$ 可能等于 0，同时 $i$ 也等于 0，如果此时是前导 0 的话不能统计到答案里面。

其他的就比较简单了，最后再开个 $\text{dp}$ 数组记忆化一下。

持续更新中……