2024 Oct

ydzr00000 / 2024-10-08 / 原文

Question 1. [Usaco2004 Dec] Fence Obstacle Course

给定 $n$ 个栅栏，第 $i$ 个栅栏的范围是 $([L_i,R_i],i)$，初始 Bessie 位于 $(S,n+1)$ 处，不能从中间跨过栅栏，但是端点处可以，问到达 $(0,0)$ 的横向移动距离最小值。

$n\leq 5\times 10^4, -10^5\leq L_i < R_i\leq 10^5, -10^5\leq S\leq 10^5$。

想一下就会发现这不是什么维护类问题，例如维护到达某一行某个特定列坐标的最短距离，考虑 DP。

设 $f_{i,0/1}$ 表示到达第 $i$ 个栅栏左/右端点的最小横向移动距离。

然后就可以 $\mathcal{O}(n^2)$ 转移，而显然一个端点往下走一定是能往下就往下，线段树预处理 $p_i,q_i$ 表示左右端点不断下落后第一个阻挡的栅栏的编号。

时间复杂度为 $\mathcal{O}(n\log_2 n)$。

Question 2. [ZJOI2010] 基站选址

有 $n$ 个村庄在一条路上顺次排列，第 $i$ 个村庄的坐标是 $D_i$，在第 $i$ 个村庄建立基站的代价是 $C_i$，你仅可以在村庄建立基站，第 $i$ 个村庄有信号当且仅当距离不超过 $S_i$ 的位置有基站，否则你需要赔偿 $W_i$ 元。

你最多建立 $k$ 个基站，试求出最小花费。

$k\leq \min(n,100), n\leq 2\times 10^4, D_i < D_{i+1}$

比较难以 DP，毕竟有这么多的参数，而且信号感应范围左边、右边均可。

设 $f_{i,j}$ 表示在第 $i$ 个村庄建立第 $j$ 个基站，且不管后面的基站如何，则转移显然是 $f_{i,j} = \underset{k < i}{\min} f_{k,j-1} + c(k,i) + C_i$ 形式，其中 $j$ 可以省略，转移 $k$ 次即可，时间复杂度为 $\mathcal{O}(n^2k)$。

问题在于这个 $c(k,i)$ 形式，考虑如何进行维护。

我们求出对于每一个村庄而言，其感应范围内最左边、最右边的村庄，记为 $L_i,R_i$，考虑如果当前位置是 $p$，将要进行 $p+1$ 的转移，对于所有 $R_i = p$ 的村庄，如果上一次建设的基站在 $[1,L_i)$ 则额外增加 $W_i$ 的代价，这一点用线段树区间加+区间最小值即可维护。

最后，我们可以向最后添加一个坐标极大、代价为 $0$ 的村庄，并将 $k\gets k+1$，这样我们会钦定最后一个必选，从而忽视掉我们的状态所带来的不足之处。

时间复杂度为 $\mathcal{O}(nk\log_2 n)$。