luogu2605

题目描述

有 个村庄坐落在一条直线上，第 个村庄距离第 个村庄的距离为 。需要在这些村庄中建立不超过 个通讯基站，在第 个村庄建立基站的费用为 。如果在距离第 个村庄不超过 的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第 个村庄没有被覆盖，则需要向他们补偿，费用为 。现在的问题是，选择基站的位置，使得总费用最小。

，，，，，，。

解题思路

考虑基本的序列dp。令 表示必须选 ，一共选的答案。那么可以比较清晰的的写出状态转移方程。 ，其中 表示两个端点为和的区间的贡献。

这个式子是比较复杂的，直接求解是的dp。我们考虑一下性质。首先当 固定时，肯定有 。对于 ，可以舍弃。进一步研究可以发现，对于，答案也可以舍弃。因此答案的贡献序列是一个随标号单增的序列。

对于这个序列，我们可以发现，如果已经求得了 ，那么的答案就是将标号从 移动到过程中新增的答案贡献。这个贡献是右端点满足的贡献的答案。

这个贡献的范围也需要考虑。左端点肯定是开始节点，右端点应该是满足的最大值。但是，当操作第层答案的时候，因为第层是没有选择任何标号的，因此更新的位置应该是而非上文提到的最大值点。

因此我们用线段树维护，在标号移动过程中不断更新相关的答案，再查询，得到。

那么如何更新最后的答案。我们发现，最后的答案相当于每个位置的答案加上最后一部分的。那么很显然，我们只需要新增一个节点即可。答案的贡献就是。

最后，注意边界条件！