C. 选区划分 详细题解

1. 问题理解

• 有一个 $2$ 行 $n$ 列的网格，$n$ 是 $3$ 的倍数。
• 每个格子是 A（阿尔瓦罗）或 J（何塞）。
• 需要将网格划分成若干个连通的 $3$ 格区块（选区）。
• 每个选区中，如果至少有 $2$ 个 A，则该选区投票给阿尔瓦罗。
• 目标：最大化阿尔瓦罗赢得的选区数量。

---

2. 关键观察

观察 1：只有 $3$ 种基本形状

由于网格只有 $2$ 行，任何 $3$ 格的连通块只能是以下几种形状：

• 水平条：一行中的连续 $3$ 格（占 $1$ 行，$3$ 列）
• L 形：$2$ 行，$2$ 列，形如：
  • 第一行 $2$ 格，第二行 $1$ 格
  • 第一行 $1$ 格，第二行 $2$ 格

注意：$2 \times 2$ 方块有 $4$ 格，不能直接使用，但可以通过两个 L 形组合。

观察 2：填充必须完整

由于网格只有 $2$ 行，如果一行中使用了水平条，另一行也必须对应地使用水平条，否则会留下无法填充的洞。

---

3. 动态规划状态设计

由于 $n$ 较大（$\le 10^5$），我们需要线性 DP。

定义 $dp[i][j]$ 表示处理完前 $i$ 列后，能获得的最大票数。其中 $j$ 表示当前列的填充状态：

• $j = 0$：前 $i$ 列完全填满（包括第 $i$ 列）
• $j = 1$：前 $i$ 列完全填满，且第 $i+1$ 列的第一行多了一个格子（即有一个 L 形伸到了下一列）
• $j = 2$：前 $i$ 列完全填满，且第 $i+1$ 列的第二行多了一个格子

---

4. 转移方程

4.1 从 $dp[k][0]$ 出发（当前列完全填满）

我们可以放置以下形状：

形状 1：两个水平条

• 第一行：列 $k+1, k+2, k+3$
• 第二行：列 $k+1, k+2, k+3$
• 覆盖 $3$ 列，新状态 $dp[k+3][0]$
• 票数增加 = 两个水平条中 A 的个数除以 $2$（每个选区需要至少 $2$ 个 A 才能赢）

形状 2：L 形（第一行 $2$ 格，第二行 $1$ 格）

• 第一行：列 $k+1, k+2$
• 第二行：列 $k+1$
• 覆盖 $2$ 列，但有一个格子伸到下一列？等一下，这个形状是 $2$ 行 $2$ 列：
  • 第一行：$k+1, k+2$
  • 第二行：$k+1$
• 这会留下第 $k+2$ 列第二行空着？不对，需要仔细。

根据标程，实际形状是：

• L 形（第一行 $2$ 格，第二行 $1$ 格）覆盖：
  • 第一行：$k+1, k+2$
  • 第二行：$k+1$
• 这占用了第 $k+1$ 列的两格，和第 $k+2$ 列的第一格。
• 剩余状态：第 $k+2$ 列的第二行是空的，但第 $k+1$ 列已满。
• 实际上，这会留下一个“突出”的格子，对应状态 $dp[k+1][2]$（第二行多一格）。

所以：

• 放置后，新状态 $dp[k+1][1]$（第一行多一格）或 $dp[k+1][2]$（第二行多一格）

票数计算：

• 对于 L 形，$3$ 个格子，票数 = 这 $3$ 格中 A 的个数是否 $\ge 2$？实际上标程用的是 /2 取整，因为每个选区最多 $1$ 票，(A个数)/2 就是是否 $\ge 2$（整数除法）。

4.2 从 $dp[k][1]$ 出发（第一行多一格）

此时，第 $k+1$ 列第一行已有一个格子（来自之前的 L 形），我们需要补全。

形状 1：两个水平条（错位）

• 第一行：列 $k+2, k+3, k+4$
• 第二行：列 $k+1, k+2, k+3$
• 这样正好填满第 $k+1$ 列的第二行，以及后续。
• 新状态 $dp[k+3][1]$

形状 2：第四种 L 形（完成填充）

• 可以放置一个 L 形，使得状态变为 $dp[k+2][0]$

4.3 从 $dp[k][2]$ 出发（第二行多一格）

对称于 $dp[k][1]$，交换行即可。

---

5. 转移公式总结

从 $dp[k][0]$：

• 到 $dp[k+3][0]$：加两个水平条
• 到 $dp[k+1][1]$：加 L 形（第一行 $2$ 格，第二行 $1$ 格）
• 到 $dp[k+1][2]$：加 L 形（第一行 $1$ 格，第二行 $2$ 格）

从 $dp[k][1]$：

• 到 $dp[k+3][1]$：加两个错位水平条
• 到 $dp[k+2][0]$：加第四种 L 形

从 $dp[k][2]$：

• 到 $dp[k+3][2]$：加两个错位水平条
• 到 $dp[k+2][0]$：加第三种 L 形

---

6. 票数计算

每个形状覆盖 $3$ 个格子，票数 = 这 $3$ 格中 A 的数量 $\ge 2$？标程使用 /2 取整：

• 如果 A 数量 = $0$ 或 $1$，/2 = 0（输）
• 如果 A 数量 = $2$ 或 $3$，`/2 = 1$（赢）

所以票数 = (A个数) / 2（整数除法）。

---

7. 初始化和答案

• 初始化：$dp[0][0] = 0$，其他为 $-\infty$
• 最终答案：$dp[n][0]$（所有列完全填满）

---

8. 时间复杂度

• 每个测试用例 $O(n)$
• $\sum n \le 10^5$，完全可行

---

9. 示例验证

以第一个测试用例为例：

3
AAA
AJJ

• 第 $1$ 列：A, A
• 第 $2$ 列：A, J
• 第 $3$ 列：A, J

最优划分：两个 L 形，每个都有 $2$ 个 A，得 $2$ 票。✅

---

10. 总结

核心思想：

1. 只有 $2$ 行，可能的 $3$ 格形状有限
2. 使用 DP 按列处理，状态表示当前列的填充情况
3. 转移时根据形状计算新增票数
4. 最终 $dp[n][0]$ 即为答案