1 条题解
-
0
题目分析
20 分
暴力搜索即可。
40 分
先考虑如何计算使得一个序列升序的最小代价。
注意到在最优解中一定不会存在操作的两个区间有交集,这是显然的,否则对两者的并集排序更优。
知道这个就好做了,首先肯定就有一个指数级的暴力了。
60 分
注意对区间 操作的代价是 。
不如从最简单的情况开始,最开始操作区间 一步到位,但是这样子很浪费。
例如序列 ,可以只对 操作,也就是说最优解是在最初状态为 的情况下不断对区间进行拆分得到的,区间拆的越多,代价和就越小。
那么一个序列升序的最小代价就十分好计算了,直接对分割点进行计算即可:
其中 表示前缀最大值, 表示后缀最小值。
对 的每一个子区间暴力算上面这个东西即可做到 的。
80 分
不如直接考虑枚举分割点在哪里,然后重新计算出 算一下上面这个式子就可以了。
时间复杂度 。
正解
注意到问题本质转化为了有多少个三元组 满足区间 的最大值小于 的最小值。
不如考虑枚举区间 的最大值 ,可以通过 set 找到前一个比 大的数的位置 ,后一个比 大的数的位置 , 后面第一个比 小的数的位置 。
那么 可以在 中选, 一定是 , 可以在 中选,贡献为 。
时间复杂度 。
- 1
信息
- ID
- 67
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者