算法标签

动态规划（DP）、状态压缩、连通性状态表示、图论（最小生成树思想）

问题分析

本题要求计算使 $( N \times K$) 网格中所有奶牛聚集到同一囚室的最小解锁代价，并统计该最小代价对应的方案数量。核心是在保证所有囚室连通的前提下，选择代价总和最小的门集合，并计数所有可能的此类集合。

关键观察

1. 网格连通性：需解锁门使网格形成连通图，最小代价对应图的最小生成树（MST），但需考虑网格的二维结构和门的方向性（水平/垂直）。
2. 状态压缩可行性：由于 $( K \leq 6$)（列数较少），可通过状态压缩表示每行内部的连通性，将每行的连通状态编码为整数，降低状态维度。
3. 动态规划转移：以行为单位，通过 DP 维护每行的连通状态及转移到下一行的最小代价和方案数，结合垂直门（连接行）和水平门（行内）的代价计算。

核心算法思路

1. 连通性状态编码

• 每行的连通状态用整数表示，编码方式为：将每行 $( K$) 个囚室的连通分量映射到 0 到 $( K-1$) 的标识（通过路径压缩思想统一标识），形成压缩后的状态码，减少状态空间。

2. 动态规划状态定义

• 定义 $( f[i][s]$) 表示处理到第 $( i$) 行，当前行的连通状态为 $( s$) 时的最小总代价及对应的方案数。状态 $( s$) 编码了该行内囚室的连通关系。

3. 状态转移与门的选择

• 水平门处理：对于每行内部的水平门（连接同一行相邻囚室），通过枚举选择哪些门解锁，更新该行的连通状态，并累加对应代价。
• 垂直门处理：考虑上下行之间的垂直门（连接相邻行的同一列囚室），通过合并上下行的连通状态，更新跨行列的连通性，并累加对应代价。
• 转移优化：利用状态压缩后的编码，通过预计算转移规则（如连通分量合并、状态转换），高效更新 DP 状态。

4. 结果计算

• 最终需所有囚室连通，即最后一行的连通状态为“所有囚室属于同一分量”。统计该状态下的最小代价对应的方案数，即为答案。

复杂度分析

• 时间复杂度：$( O(N \cdot S \cdot T)$)，其中 $( S$) 为压缩后的状态数（因 $( K \leq 6$)，$( S$) 约为 $( 10^5$) 级别），$( T$) 为每个状态的转移数（与 $( K$) 相关，可控）。对于 $( N \leq 3 \times 10^4$)，整体复杂度可接受。
• 空间复杂度：$( O(S)$)，通过滚动数组优化 DP 空间，仅需存储当前行和上一行的状态，空间开销可控。

总结

本题通过状态压缩将高维连通性问题转化为低维整数编码，结合动态规划高效追踪最小代价及方案数。核心在于利用 $( K$) 较小的特性，将每行连通状态压缩为可管理的整数，再通过预计算转移规则实现高效的状态更新，最终在保证连通性的前提下，得到最小代价的方案数量。