1 条题解

  • 0
    @ 2026-11-15 13:45:10

    题目分析

    20 分

    暴力搜索即可。

    40 分

    需要挖掘一些性质,考虑到最终留下来的序列是原序列的一个子序列。

    那么一个合法的子序列需要满足什么性质。

    假设这个子序列是 Ai1,Ai2,...,Aik(i1<i2<...<ik)A_{i_1},A_{i_2},...,A_{i_k}(i_1<i_2<...<i_k),该子序列合法的充要条件是:

    • ∀1≤j<i1\forall 1\le j< i_1,Aj>Ai1A_j>A_{i_1}。
    • ∀ik<j≤n\forall i_k< j\le n,Aj>AikA_j>A_{i_k}。
    • ∀ip<j<ip+1\forall i_{p}<j<i_{p+1},Aj>AipA_j>A_{i_p}或者 Aj>Aip+1A_j>A_{i_{p+1}}。

    这个条件是显然的,因为如果区间 [ip+1,ip+1−1][i_p+1,i_{p+1}-1] 的最小值比两边留下来的数都小,那么这个数肯定删除不了。

    知道这个就好搞了,暴力搜索枚举即可,复杂度是指数级的。

    60 分

    注意到这个是 dp 的,设 dpidp_i 表示选到了 ii(强制选 ii)的最长合法的子序列长度。

    转移是 easy 的,枚举上一次的转移点,合法条件暴力 check 即可,时间复杂度是三方的。

    80 分

    每次判断合法没必要暴力 check,知道这个区间的最小值就行了,于是从后往前维护最小值即可。

    时间复杂度是两方的。

    正解

    考虑优化,设 posipos_i 表示 aia_i 左边第一个比它小的数的位置。

    枚举上一次的转移点 jj。

    • j∈[posi+1,i−1]j\in [pos_i+1,i-1],注意到这样的转移点一定是合法的,前缀和优化即可。
    • j≤posij\le pos_i,如果 aj>aia_j>a_i,那么这个转移点显然不合法,否则需要满足 min⁡k=jiak=aj\min_{k=j}^i a_k=a_j,即所有后缀最小值的位置都是合法的转移点,维护一个 gk=fk+flk+fllk+....g_k=f_{k}+f_{l_k}+f_{l_{l_k}}+.... 即可。

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

    • 1

    信息

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