本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-15 22:56:39

我承认我的动态规划真的非常烂，所以我决心要恶补一下。

Ad maiora!

P1095 [NOIP2007 普及组] 守望者的逃离

贪心。下面证明。

证明

问题是求在 $T$ 秒内能走的最长距离。有几种选择：

• （操作 A） 不动，恢复 4 点魔法值
• （操作 B） 移动 17 单位
• （操作 C） 移动 60 单位，使用 10 点魔法值

我们要证明的是本问题的最优子结构。如果我们已经有了走到 $t - 1$ 时间的最优解 $P_{1, t - 1}$，要证走到 $T$ 时间的最优解一定包含 $P_{1, t - 1}$ 。

用标准的 cut-and-paste。设 $Q_{1, t}$ 才是到 $t$ 时间的最优解，那么一定有 $Q_{1, t - 1} \gt P_{1, t - 1}$。

• 如果 $Q_T$ 是操作 A，那么 $\lvert Q_{1,t}\ert = \lvert P_{1,t-1}\rvert$。矛盾，得证。

• 如果 $Q_T$ 是操作 B，那么明显将 $P_{t-1}$ 嫁接到 $Q$ 上对其没有任何影响，况且可以得到 $\lvert Q_T\rvert \gt \lvert Q_{1, t} - Q_{1, t-1} + P_{1, t-1}\rvert$。矛盾，得证。

• 如果 $Q_T$ 是操作 C，那么我们知道 $M_Q(t-1) \ge 10$。我们要证 $M_P(t-1) \ge 10$。

• （情况 1）： 如果正如此，那么没有什么好证明的。

• （情况 2）： 如果并非如此，即 $M_P(t-1) < 10$，这就意味着 $P_{1,t-1}$ 一定比 $Q$ 多至少一次操作 C，$Q_{1,t-1}$ 一定比 $P$ 多至少一次操作 A，因此 $\lvert P_{1,t-1}\rvert - \lvert Q_{1,t}\rvert \ge 60$。于是，$\lvert Q_{1,t}\rvert + 60 \le \lvert P_{1,t-1}\rvert$，更有 $\lvert Q_{1,t}\rvert + 60 \lt \lvert P_{1,t-1}\rvert + 17$。这也就是说 $Q_{1,t}$ 甚至比不上 $P_{1,t-1}$。这显然是矛盾的，得证。

于是得证。

归纳

归纳边界：当 $t = 0$ 时明显最大距离为 0。

设 $t$ 对于本问题是前 $t$ 秒的最优解，那么对于前 $t + 1$ 秒，由于最优子结构性质，我们只需要考虑在操作 A、B 与 C 中进行选择，选择最大者即可。

P1359 租用游艇

最优子结构易证。

我们设 $f(i)$ 表示从 $1$ 到 $i$ 的最小租金。归纳边界是 $f(1) = 0$。

要走到第 $i$ 个回收站，我们可以从 $1, \cdots, i - 1$ 的回收站里选一个进行租用。那么方程就是

$$ f(i) = \begin{cases} 0 & i = 1 \ \min\limits_{1\le j\lt i} f(j) + r(j, i) & \text{otherwise} \end{cases} $$

P1566 加等式

计数 DP。要求的是方案数量。设 $f(i, j)$ 是在这个集合的前 $i$ 个元素中表示 $j$ 的方案数。

归纳边界明显：$f(i, 0) = 1$。

一般地，要表示 $j$，只有两种方法：$j$ (1) 和 $(j - p_i) + p_i$。那么，表示出 $j$ 的方案数，就是原来的方案数量加上 $f(i - 1, j - p_i)$

但是最终的答案要减去每一个 (1)。即，最终的答案要减去 $m$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 12:46:56

对于原问题，这就是一个简单的计数 DP。设 $f(i)$ 是将这些物品放进体积为 $i$ 的背包内的方法数量，则转移方程是

$$ f(i) = \begin{cases} 0 & i = -1 \ 1 & i = 0 \ \sum\limits_{j = 0}^{n} f(i - \min (w_j, i + 1)) & \text{otherwise} \end{cases} $$

写成代码便是

rep (i, 0, n) rrep (j, v, w[i]) dp[j] += dp[j - w[i]];

对于本问题，我们要求的是删除某个物品 $i$ 后的最大容积。

明显我们有以下等式：

$$ f(n) = f(n - w_0) + f(n - w_1) + \cdots f (n - w_{i}) + \cdots + f(n - w_k) $$

删除物品 $i$ 后的 $f(n)$ 应当减去 $f(n - w_i)$。于是，我们可以计算出去除了 $i$ 后的 tp：

rep (i, 0, n) rep (j, 0, v + 1)
  if (j < w[i]) tp[j] = dp[j];
  else tp[j] = dp[j] - dp[j - w[i]];

这个复杂度是 $O(nV)$ 的，显然能够通过。

编码时注意取模即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 13:08:04

本题的特点是 $W$ 极大，而 $v_i$ 与 $N$ 却较小。求的是在总重量小于等于 $W$ 的前提下的最大价值。

我们可以进行一个简单的思维转换：将问题转换为价格最大时的最小重量。也即，将价格作为状态，求出价格为某时的最小体积。

之后我们自后往前遍历 dp 数组并找到第一个满足 dp[i] <= w 的 $i$。此时 $i$ 就是最大的价格。

归纳边界：dp[0] = 0

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 14:11:14

本题是要求序列中的 $\max \sum\limits_{i=0}^{\lvert x\rvert -1 } A_{x_i} \le T$。

注意到 $N \le 40$，无法直接进行子集枚举。但是如果我们将其分为两半，那么 $N' \le 20$，这时进行子集枚举可行。

于是我们就在 $A =T_1, \cdots, T_{\lfloor N/2\rfloor}$ 与 $B =T_{\lceil N/2\rceil}, \cdots, T_N$ 上进行子集枚举，求出每种状态的和。

最后，我们将两个子问题的解组合在一起：在其中一个子集上进行遍历：对 $A_i$，我们需要找到一个 $B_j$ 使得 $A_i + B_j$ 最大且小于等于 $T$。

这就是 upper_bound 的上一个元素。用指针就是 upper_bound (...)[-1]。取最大值即可。

源代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 15:43:16

重心的定义与性质

一棵树的重心是这样的点：将它删除后，它的所有子树的节点数量的最大值，在所有节点中最小。

重心最重要的性质是：一棵树上所有点到重心的距离和是最短的。

重心的求法

我们可以用一个简单的 DFS 算法来求重心。

对每一个节点，我们在 DFS 中统计它的子树节点数量，并且取得其最大值 $t$。我们知道，将这个节点删除后，整个图中除了它的子树，还有它的父亲所在的子树。它父亲所在的子树的节点数量，很明显是树的总节点数量减去这个节点的子树节点数量，也就是 $n - t$。

设 $p = \max (n - t, t)$，则我们只需要找到使 $p$ 最小的节点即可。

int
centroid (int p, int father)
{
  int weight = 0;
  sizep[p] = 1;

  for (auto t : e[p])
      if (t != father) weight = max (weight, sizep[p] += centroid (t, p););

  weight = max (weight, n - sizep[p]);
  if (weight < mw) mw = weight, center = p;
  return sizep[p];
}

则 center 就是重心。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-19 21:48:04

题目要求的是一个区间内的平均数和方差。很明显是线段树的题目。

容易得到：

$$ \begin{aligned} s^2 & = \frac 1 n \sum\limits_{i=1}^n (x_i - \bar x)^2 \ & = (x_1 - \bar x)^2 + (x_2 - \bar x)^2 + \cdots + (x_n - \bar x)^2 \ & = x_1^2 + x_2^2 + \cdots x_n^2 + n\bar x^2 - 2\bar x(x_1 + x_2 + \cdots + x_n) \ & = \sum\limits_{i=1}^n x_i^2 -2\bar x \sum\limits_{i=1}^n x_i + n\bar x^2 \ & = \frac 1 n\sum\limits_{i=1}^n x_i^2 -\frac 1 {n^2} (\sum\limits_{i=1}^n x_i)^2 \end{aligned} $$

于是对一个区间，我们只需要维护它的总和以及平方和即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-20 19:32:04

本题很明显是动态规划。

可以用完全背包的思路来做：每一件纪念品一天能买无数次，将背包容量设为当前拥有的金币数量，将体积设为今天的价值，将价值设为明天的价值。

这样使用完全背包即可。

为什么？因为题目中有比较重要的一条：当日买进的纪念品也可立马卖出。因此，我们可以将价值设为今天与明天的价格差。

于是转移方程就是：

$$f(i, j) = \max {f(i - 1, j - P_{i,j}) + P_{i+1,j} - P_{i, j}, f(i - 1, j)}$$

本题告诉了我们背包模型的常见：对于很多作出选择的动态规划，我们都可以将其归为 01 背包、完全背包或者多重背包的一种。重点在于怎么设出正确的状态，也即 容量、体积 与 价格。这三者缺一不可。

明显，体积和价格是每一个物品所具有的属性。体积是作出选择所要付出的代价，而价格是所能获得的利益。而容量是转移方程中所变化的量，容量的变化能够影响当前的决定。

根据这些量来将题目抽象化，就可能将难以解决的问题归为背包问题。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-21 15:10:00

本题的特点是每个点上要加的值是不一样的，但是差值之间是一样的。

这让我们想到差分。

事实上，我们可以对这个序列进行差分。这样，点 $p$ 的值就是 $\sum\limits_{i=1}^p d_i$。这恰好就是线段树所可实现的区间更改和区间查询。

更新区间 $[l, r]$ 时，我们需要将 $l$ 点加上 $k$，将 $[l+1, r]$ 上每个点加上公差 $d$，最终在 $r + 1$ 点处减去 $a_{r - l + 1}$，即 $k + d\times (r - l)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-21 20:56:05

这两道题都是状态压缩的题目。

P1879 [USACO06NOV] Corn Fields G

我们知道，对于一个状态 j，为了使它每一个 $1$ 之间不相邻，我们有 j & (1 << j) 为零。而要使它与前一行的状态 $k$ 不冲突，我们需要有 j & k 为零。

这就告诉我们怎么进行状态之间的转移。我们设 $f(i, j)$ 表示第 $i$ 行，状态为 $j$ 的时候的方案数。我们知道，$f(i, j)$ 可以由 $f(i - 1, k) \text{ s.t. } k \text{&} j = 0$ 转移而来，其中 $k$ 表示的是前一行的状态。

最终，我们有

$$ f(i,j) = \begin{cases} 0 & i = 0, j = 0\ \sum\limits_{k & j = 0} f(i-1,k) & \text{otherwise} \end{cases} $$

最终我们要统计的就是第 $m$ 行所有状态的方案数量和。

P1171 售货员的难题

旅行商问题嘛。依然是设状态 $f(i, j)$， 表示由状态 $j$ 走到第 $i$ 个点的最短距离，其中 $i \notin j$。

我们如果知道了 $f(i, j)$，就可以推出 $f(i, j\cup \{k\}) = f(i,j) + P_{j, k}$。归纳边界 $f(0, 1) = 0$。

我们要求的就是在最终的满状态里选一点，从这一点走到 $0$，找最小值。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-23 09:51:40

这道题的转移方程还不算难列：

$$ f(i, j) = \begin{cases} \frac 1 2 f(i, i) & j = 1 \ \frac 1 2 f(i - 1, j - 1) + \frac 1 2 f(i, j - 1) & \text{otherwise} \end{cases} $$

但是问题是，这个转移方程是带环的：

$$ \begin{aligned} f(2, 1) = \frac 1 2 f(2, 2) \ f(2, 2) = \frac 1 2 f(2, 1) + \frac 1 2 f(1, 1) \end{aligned} $$

但是我们发现，这个方程组是有通解的：

$$ \begin{aligned} f(n, 1) = \dfrac {\sum\limits_{i=1}^{n - 1} 2^{i-1} \times f(n - 1, i)}{2^n - 1} \ f(n, i) = \frac 1 2 f(n - 1, i - 1) + \frac 1 2 f(n, i - 1) \end{aligned} $$

于是，$f(n, 1)$ 的计算是 $O(n)$ 的，而 $f(n,i), \text{s.t.} \space i \neq 1$ 的计算是 $O(1)$ 的。

然后推出即可。