「Summary」2022-06-30 做题记录

《简单 DP》

2022-06-30

$\mathbb{JOISC 2020 \ Day4 T3}$

link

我不理解你不理解啥？

首先读完题，误入歧途，随手一个状态 $dp[i][s]$ 表示，用了前 $i$ 个治疗计划，当前所有人的状态压缩成二进制串是 $s$ 。

看到数据范围 $n \le 1e9$ 直接劝退。

重新思考，这道题有三个关键的维度，一个是时间，一个是所有人的状态，还有一个是花费。

再进一步分析每个治疗计划，依次执行，把治好理解成染色，脑补一下感觉就像是 $n$ 个块，一开始是空的，你花一个代价，使一个连续的区间在某个时刻全部变成黑的，然后随着时间的推移，每过一个单位的时间，这些连续的黑色的区间两端的黑色块就变成白色，要求是在某个时刻所有块都是黑色并且要求花的代价最小。

然后抽象成一堆会越来越短的区间不断组合拼成一个大的区间。

而使整个区间联通的条件就转化成了使 $1$ 和 $n$ 联通，这就把问题拉到图上来，要求的答案则是完成该条件的最小代价，也可以理解为 $1$ 到 $n$ 的最短路。

而两个操作 $i,j$ （这里钦定 $i$ 操作的区间在 $j$ 操作的区间前） 可以拼一起的条件则是 $\mid t_i - t_j \mid \le r_j - l_i + 1$ 。

这个时候我们则可以在这两个区间中连一条有向边 $w(i, j) = c_j$。

那么用 dijsktra 就能解决。

实现中找可拼接的区间可以把绝对值拆开，以 $t$ 作为下标，用两个线段树维护。

$\mathbb{Lanterns}$

link

前缀是个好东西

定义 $dp_i$ 表示前 $i$ 个灯笼能够覆盖的最长前缀。
然后大力分类讨论。

• 如果前 $i-1$ 个灯笼照不到第 $i$ 个，直接 $dp_{i - 1} = dp_{i - 1}$ 。

• 如果前 $i - 1$ 个灯笼能照到第 $i$ 个，那么 $dp_i = \max(i + p_i, dp_{i - 1})$ 。

• 如果让这个灯笼往前照，就像这样

• 其中要在前 $i - 1$ 个灯笼中找到最前面的一个 $t$ 使得 $dp_t > i - p_i$ ，那么我们可以用 $i,t$ 两个灯笼把 $[t+1,i-1]$ 中的所有灯笼照亮，所以 $[t+1,i-1]$ 中的所有灯笼可以全部朝右。需要找到一个 $j$ 的使得 $j+p_j$ 最大，则 $dp_i = \max(dp_i, j + p_j)$ 。这个过程可以用线段树维护。

整道题的复杂度为 $\Theta(n \log_2n)$ ，瓶颈在于使灯笼往回照时找 $t$ 和 $j$。