1 条题解
-
0
题目分析
棋(chess)题解
这类问题有一个通用的算法是状压 dp,把计算贡献要用到的格子的状态都记下来。在这里就是 表示前 列均已确定颜色,同时第 列的染色状态分别为 所能获得的最大答案。
但是你会发现这样子一个格子可能被计算多次贡献,为了防止这一点,有两种方法。第一种是本着“哪些信息影响后续决策就记录哪些信息”的思想,多记两维表示第 列的每个格子是否已经算在了答案里,这样枚举下一列的染色状态就能转移了。第二种是一个很巧妙的手法,那就是在状态里记录前 列的染色状态,转移时枚举下一列,这样得到一个 的矩阵,我们只计算中间那一列格子的贡献,这样就不会算重了。这两种算法的状态都是 级别。
- 1
信息
- ID
- 138
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者