文章目录

洛谷 P3035 Umbrellas for Cows S 做题笔记

发布于

有 $N$ 只奶牛,奶牛 $i$ 的位置是 $X_i$。
有 $M$ 种雨伞,第 $i$ 种雨伞的价格为 $C_i$,宽度为 $i$。
现在想买一些雨伞,使得每头奶牛都在伞下。求最少花费。
注意,大伞不一定比小伞贵,伞可以重叠。

$1 \leq N \leq 5000, 1 \leq M \leq 10^5, 1 \leq X_i \leq M$

题解

首先,应该将伞的价格做后缀最小值。因为伞可以重叠,所以小的伞必然可以被大的伞取代。

然后,按 $X$ 从小到大排序,这样方便 DP。

接下来设 $f\left(i\right)$ 表示覆盖区间 $\left[1, i\right]$ 的最小花费。

则转移就是

$$f\left(i\right) = \min\limits_{j = 1}^i \{f\left(j - 1\right) + C\left[X_i - X_j + 1\right]\}$$

时间复杂度 $\mathcal O\left(N^2\right)$。

代码


暂无评论

发表评论