1 条题解

  • 0
    @ 2026-11-15 16:45:30

    题目分析

    20pts

    f[i][j]f[i][j] 表示 bi=jb_i=j 的情况下,填入 bb 序列的前 ii 项的方案数。

    那么f[i][j]f[i][j] 可以转移到 f[i+1][k]f[i+1][k] 当且仅当 j≤bi,k≤bi,j≠kj \leq b_i,k \leq b_i, j≠k,假设值域为 VV,时间复杂度为 O(nV)O(nV)。

    40pts

    首先直觉告诉我们合法方案数不好求,所以正难则反考虑求不合法的情况,不合法的情况也不好求,但是我们可以比较自然地想到容斥。

    也就是求 F(i)F(i) 表示至少有 ii 个坏点的方案数。

    然后考虑动态规划,设 fi,jf_{i,j} 表示前 ii 项划分成 jj 部分,部分内部是相同的数字,但是相邻的部分不要求不同(因为你是容斥,保证至少多少个不同即可)。

    显然 F(i)=fn,n−iF(i)=f_{n,n−i}。

    我们发现这个东西和最小值有关系,一个部分的取值方案就是最小值,这点比较显然。

    转移为

    $$f_{i,j}=\sum_{k=1}^{i-1} f_{k-1,j-1} \times \min_{x=k}^j a_x$$

    时间复杂度为 O(n3)O(n^3)。

    60pts

    我们并不关心 jj 的具体大小,只关心 jj 的奇偶性,因为容斥系数为 (−1)n−j(-1)^{n-j},所以每取一段,就让方案数乘上 −1-1,我们可以忽略掉 jj 这一维

    $$f_{i}=\sum_{k=1}^{i} -f_{k-1} \times \min_{x=k}^j a_x$$

    时间复杂度为 O(n2)O(n^2)。

    100pts

    考虑怎么维护 min⁡x=kjax\min_{x=k}^j a_x,可以维护单调栈的具体形态,利用前缀和在单调栈变化时进行 DP 转移,时间复杂度为 O(n)O(n)。

    • 1

    信息

    ID
    139
    时间
    2000ms
    内存
    1024MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者