1 条题解

  • 0
    @ 2026-11-15 16:24:44

    题目分析

    数据点 1

    每个位置只有一种取值,直接使用 LIS 算法即可。

    数据点 2~3

    考虑 DP,设 dpi,jdp_{i,j} 为确定了前 ii 个数,aia_i 确定为 jj 的 LIS。

    那么有转移方程:dpi,j=max⁡(dpk,l+1),k<i,l<jdp_{i,j} = \max(dp_{k,l} + 1),k < i,l < j。

    数据点 4~6

    考虑开一个数据结构维护转移,在求出所有 dpi,jdp_{i,j} 后,往这个数据结构里面加二元对 (j,dpi,j)(j,dp_{i,j}),只要每次在这个数据结构里面选转移,就满足了 k<ik < i 的限制。

    对于第二维的限制,发现这个数据结构需要支持:

    • 插入一个二元组 (x,y)(x,y)。
    • 查询 x≤kx \le k 的最大 yy。

    使用线段树即可。

    数据点 7~10

    由题意易知 1≤dpi,j≤n1 \le dp_{i,j} \le n,而对于相同的 DP 值,jj 越小一定越优秀,于是我们可以让这个数据结构时刻只存在 O(n)O(n) 个转移。

    接下来让数据结构中所有值按照 xx 排序,并且对 aia_i 的 kk 个取值进行排序,然后进行双指针即可完成转移。

    于是就在 O(n2+nk)O(n ^ 2 + nk) 的时间复杂度内解决了该问题。

    • 1

    信息

    ID
    126
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者