题解

思路

先只考虑一层。若暂时把每个明亮窗口都看作一套有人居住的一居室，那么数量等于这一行中 1 的个数 $c$。

选择一对相邻窗口作为两居室时，只有 11 会把原来的两个有人居住公寓合并为一个，使答案减少 $1$；00、01、10 都不会改变相对于 $c$ 的计数。因此问题等价于：在长度为 $m$ 的路径上选择恰好 $k=\frac m4$ 条互不相邻的边，分别最大化和最小化被选中的 11 边数。

做法

子任务 1：枚举所有合法布局

当 $m\le12$ 时，可以从左到右递归。当前位置既可以作为一居室，也可以与右侧窗口组成两居室；记录已经选择的相邻对数量以及其中 11 的数量。只统计恰好选择 $k$ 对的方案，就能得到 11 对数的最小值和最大值。

一行至多枚举 $O(2^m)$ 个递归状态，总时间复杂度为 $O(n2^m)$，递归空间复杂度为 $O(m)$。

子任务 2：路径上恰好选若干边的动态规划

令 $f_{i,j}$ 表示只看前 $i$ 个窗口、恰好选择 $j$ 对相邻窗口时，所选 11 对数的最小值或最大值。转移有两种：

• 第 $i$ 个窗口单独放置，从 $f_{i-1,j}$ 转移；
• 把第 $i-1,i$ 个窗口组成两居室，从 $f_{i-2,j-1}$ 转移，并根据这两个字符是否都是 1 加上 $0$ 或 $1$。

分别维护最小值和最大值即可。当 $m\le100$ 时，总时间复杂度为 $O(nm^2)$，空间复杂度为 $O(m^2)$，也可以用滚动数组优化。

子任务 3：两次路径匹配贪心

最小化有人居住的公寓数

需要尽量多选 11 对。对一行从左到右扫描：一旦遇到相邻的 11，就选中这一对并跳过两个位置。对路径上的同类边，选择最靠左的可用边不会妨碍后续，因而得到 11 边的最大匹配数 $p_{11}$。

实际只能选 $k$ 个两居室，所以最多合并 $\min(k,p_{11})$ 对。该行对最小值的贡献为

最大化有人居住的公寓数

需要尽量用 00、01、10 这些非 11 对占据两居室名额。再次从左到右扫描，一旦当前相邻对不是 11，就选中并跳过两个位置。得到非 11 边的最大匹配数 $p_0$。

若 $p_0<k$，剩余 $k-p_0$ 个两居室必然是 11；否则可以完全避免合并两个明亮窗口。因此该行对最大值的贡献为

各层布局互不影响，把每行的两个贡献分别求和即可。

正确性说明

在路径上只允许选互不相邻的边。对某一类允许边，从左到右选择第一条可用边后，任何最优匹配若没有选择它，都可以把其最左侧、与它冲突或更靠右的第一条边替换成它，匹配大小不会减少，后面的可选范围也不会缩小。故上述两次贪心分别得到 11 边和非 11 边的最大匹配数。

任意合法布局的有人居住数都等于明亮窗口数减去被选中的 11 对数。第一种贪心给出这个对数的最大可能值，第二种贪心给出能先使用的非 11 对的最大数量，从而确定不得不使用的 11 对的最小数量。两式分别就是本层的最小值与最大值。逐层取极值并相加仍可同时实现，因为每层布局可以独立选择。

复杂度

满分做法对每个窗口只扫描常数次，时间复杂度为 $O(nm)$，额外空间复杂度为 $O(1)$（不计输入字符串）。答案不超过 $n\cdot m$，使用 64 位整数保存总和。