1 条题解

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

    题目分析

    棋(chess)题解

    这类问题有一个通用的算法是状压 dp,把计算贡献要用到的格子的状态都记下来。在这里就是 f(i,s1,s2)f(i,s1,s2) 表示前 ii 列均已确定颜色,同时第 i,i−1i,i-1 列的染色状态分别为 s1′,s2′s1',s2' 所能获得的最大答案。

    但是你会发现这样子一个格子可能被计算多次贡献,为了防止这一点,有两种方法。第一种是本着“哪些信息影响后续决策就记录哪些信息”的思想,多记两维表示第 i,i−1i,i-1 列的每个格子是否已经算在了答案里,这样枚举下一列的染色状态就能转移了。第二种是一个很巧妙的手法,那就是在状态里记录前 44 列的染色状态,转移时枚举下一列,这样得到一个 3×53\times 5 的矩阵,我们只计算中间那一列格子的贡献,这样就不会算重了。这两种算法的状态都是 212×n2^{12}\times n 级别。

    • 1

    信息

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