题意
有 $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)$。