1 条题解

  • 0
    @ 2026-11-15 13:33:25

    题目分析

    20 分

    暴力搜索即可。

    40 分

    先考虑如何计算使得一个序列升序的最小代价。

    注意到在最优解中一定不会存在操作的两个区间有交集,这是显然的,否则对两者的并集排序更优。

    知道这个就好做了,首先肯定就有一个指数级的暴力了。

    60 分

    注意对区间 [l,l][l,l] 操作的代价是 00。

    不如从最简单的情况开始,最开始操作区间 [1,n][1,n] 一步到位,但是这样子很浪费。

    例如序列 1,3,2,5,41,3,2,5,4,可以只对 [1,3],[4,5][1,3],[4,5] 操作,也就是说最优解是在最初状态为 [1,n][1,n] 的情况下不断对区间进行拆分得到的,区间拆的越多,代价和就越小。

    那么一个序列升序的最小代价就十分好计算了,直接对分割点进行计算即可:

    n−1−∑i=1n−1[prei<sufi+1]n-1-\sum_{i=1}^{n-1}[pre_i<suf_{i+1}]

    其中 preipre_i 表示前缀最大值,sufisuf_i 表示后缀最小值。

    对 AA 的每一个子区间暴力算上面这个东西即可做到 O(n3)\mathcal{O}(n^3) 的。

    80 分

    不如直接考虑枚举分割点在哪里,然后重新计算出 pre,sufpre,suf 算一下上面这个式子就可以了。

    时间复杂度 O(n2)\mathcal{O}(n^2)。

    正解

    注意到问题本质转化为了有多少个三元组 (i,j,k)(i≤j<k)(i,j,k)(i\le j< k) 满足区间 [i,j][i,j] 的最大值小于 [j+1,k][j+1,k] 的最小值。

    不如考虑枚举区间 [i,j][i,j] 的最大值 xx,可以通过 set 找到前一个比 xx 大的数的位置 aa,后一个比 xx 大的数的位置 cc,cc 后面第一个比 xx 小的数的位置 dd。

    那么 ii 可以在 (a,b](a,b] 中选,jj 一定是 c−1c−1,kk 可以在 [c,d)[c,d) 中选,贡献为 (b−a)×(d−c)(b−a)×(d−c)。

    时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。

    • 1

    信息

    ID
    67
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者