1 条题解
-
0
题目分析
- 考虑动态规划,观察发现:操作能除去草和位置无关,所以先将草的高度排序。
- 每次操作除去比最高草的高度的一半低的草,最坏情况就是只能除一株草,也就是次高的草是最高草的高度的一半,设最高草的高度为 (h),那么最多操作次数为 (\log_2(h)) 次,约为 30。
- 状态定义:(dp_{i,j}) 表示除去前 (i) 株草操作 (j) 次的最小提前除草次数。
- 状态转移:
- 除去第 (i) 株草有两种方法:
- 提前除草:(dp_{i,j} \leftarrow dp_{x,j-1});
- 操作除草:(dp_{i,j} \leftarrow dp_{i-1,j} + 1)。
- 所以最后的转移方程就是 (dp_{i,j} \leftarrow \min(dp_{i-1,j-1}, dp_{x,j} + 1))。其中 (x) 是低于第 (i) 株草高度一半的草中最高的草最大的下标(可以用二分求)。
- 最后答案只要遍历操作次数,遇到一个有答案的 (i) 就直接输出 (i) 和 (dp_{n,i})。
- 时间复杂度:。
5
20pts
问题相当于求解两两点对之间的最短路距离,乘上一个权重后的结果。
考虑对于每次询问,使用 算法在 的时间复杂度内求解两两点对之间的最短路距离,总复杂度为。
60pts
对于第 天,答案显然为 $\sum_{1 \leq i,j \leq n} c_{i,j} \times \text{dist}'(i,j)$ 其中 表示将对应路径的边权设为 以后 的最短路。
先跑出原图两两点之间的最短路 。
假设在这一天,清零的道路为 ,那么对于点对 ,其变化的路径权值为 $\max(0,\text{dist}(i,j)-\text{dist}(i,x)-\text{dist}(y,j),\text{dist}(i,j)-\text{dist}(i,y)-\text{dist}(x,j))$ 即讨论是否走过 这条道路,从而更新修改后的图的最短路,时间复杂度为 。
100pts
上述式子等于 $\max(0,\text{dist}(i,j)-\text{dist}(i,x)-\text{dist}(y,j))+ \max(0,\text{dist}(i,j)-\text{dist}(i,y)-\text{dist}(x,j))$ 考虑如何证明,即说明 和 不能同时大于,我们利用反证法,假设二者同时大于 ,那么将两式相加,有 $2\text{dist}(i,j)>\text{dist}(i,y)+\text{dist}(y,j)+\text{dist}(i,x)+\text{dist}(x,j)$ 而由于最短路的性质,有 $\text{dist}(i,j) \leq \text{dist}(i,y)+\text{dist}(y,j)$
$\text{dist}(i,j) \leq\text{dist}(i,x)+\text{dist}(x,j)$
两式相加,和上面的式子矛盾,所以成立。
问题变成了如何求解 $\sum_{1 \leq i,j \leq n}c(i,j) \times\max(0,\text{dist}(i,j)-\text{dist}(i,x)-\text{dist}(y,j))$ 固定 后将所有 从小到大排序,然后枚举 ,可以利用双指针快速计算所有答案,时间复杂度为。
- 1
信息
- ID
- 210
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者