1 条题解

  • 0
    @ 2026-11-15 14:20:04

    题目分析

    20 pts

    指数暴力枚举每个机遇选或不选

    50 pts

    考虑一个 DP

    f(i,j,k)f(i, j, k) 表示经过 ii 次机遇后,aj>aka_j > a_k 的方案数

    如何统计答案?

    答案就是所有满足 i<ji < j 的 f(m,i,j)f(m, i, j) 之和

    如何转移?

    枚举状态 i,j,ki, j, k,设第 ii 次机会是交换 axa_x 和 aya_y

    若 x,yx, y 和 j,kj, k 完全不同,则 f(i,j,k)=2×f(i−1,j,k)f(i, j, k) = 2 \times f(i - 1, j, k)

    若 x=j,y≠kx = j, y \neq k,则 f(i,j,k)=f(i−1,x,k)+f(i−1,y,k)f(i, j, k) = f(i - 1, x, k) + f(i - 1, y, k),f(i,k,j)=f(i−1,k,x)+f(i−1,k,y)f(i, k, j) = f(i - 1, k, x) + f(i - 1, k, y)

    若 x=j,y=kx = j, y = k,则 f(i,j,k)=f(i−1,j,k)+f(i−1,k,j)f(i, j, k) = f(i - 1, j, k) + f(i - 1, k, j)

    复杂度 O(n3)O(n^3)

    100 pts

    怎么优化?

    第一维可以滚动数组。

    注意到,每次转移只有 O(n)O(n) 个位置不是 ×2\times 2,其他 O(n2)O(n^2) 个位置都是 ×2\times 2

    那么通过这个观察,我们能否优化掉这 O(n2)O(n^2) 个位置的转移呢?

    答案是可以的,我们设

    g(i,j,k)=f(i,j,k)2ig(i, j, k) = \frac{f(i, j, k)}{2^i},这样每次就不需要 ×2\times 2 了,最终答案 ×2m\times 2^m 即可

    时间复杂度 O(nm)O(nm)

    • 1

    信息

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