正方形法阵思路
2025-08-06 16:05:12
发布于：浙江
0阅读
0回复
0点赞
问题分析：
需要在 n×n 的方格中放置药水，满足每个 2×2 的子矩阵恰好包含 2 瓶药水，目标是最大化所有放置药水的法力值总和。
核心观察：
满足 "每个 2×2 子矩阵恰好有 2 瓶药水" 的放置方式存在两种基础模式，这两种模式能覆盖所有可能的最优解：
- 行交替模式：对于每一列，选择要么在奇数行放置药水，要么在偶数行放置药水。这种模式下，任意 2×2 子矩阵会包含恰好 2 瓶药水（上下两行各 1 列选择不同）。
- 列交替模式：对于每一行，选择要么在奇数列放置药水，要么在偶数列放置药水。这种模式下，任意 2×2 子矩阵同样会包含恰好 2 瓶药水（左右两列各行选择不同）。
算法核心：
分别计算两种模式下的最大可能法力值总和，取其中的最大值作为答案。
步骤分解：
- 行交替模式计算（Family A）：
o 遍历每一列，分别计算该列中所有奇数行（1-based）的法力值总和，以及所有偶数行的法力值总和。
o 对每一列，选择上述两个总和中的较大值，累加得到行交替模式的总法力值。 - 列交替模式计算（Family B）：
o 遍历每一行，分别计算该行中所有奇数列（1-based）的法力值总和，以及所有偶数列的法力值总和。
o 对每一行，选择上述两个总和中的较大值，累加得到列交替模式的总法力值。 - 结果：
o 行交替模式与列交替模式的总法力值中的最大值，即为满足条件的最大可能法力值。
这里空空如也
有帮助，赞一个