题目描述

难度分:$1500$

输入一个$2$行$n(\leq 100)$列的棋盘。

用数字0表示空格子，大写字母X表示一开始就被占据的格子。

你有无数个L形状的积木，可以旋转，也就是如下$4$种形状：

XX   XX   0X   X0
X0   0X   XX   XX

积木只能放在空格子上（占据$3$个空格子），不能放在被占据的格子上。积木之间不能重叠。

问：最多可以往棋盘上放多少个积木？

输入样例$1$

00
00

输出样例$1$

1

输入样例$2$

00X00X0XXX0
0XXX0X00X00

输出样例$2$

4

输入样例$3$

0X0X0
0X0X0

输出样例$3$

0

输入样例$4$

0XXX0
00000

输出样例$4$

2

算法

状压DP

这种计数类问题比较容易想到DP，考虑到棋盘只有$2$行，极有可能就是枚举状态转移的情况，并在行方向上对列状态进行状态压缩。

状态定义

定义以下$4$种状态分别为$0$，$1$，$2$，$3$

$state=0$

0
0

$state=1$

X
0

$state=2$

0
X

$state=3$

X
X

即X代表二进制位上的$1$，0代表二进制位上的$0$。$dp[i][state]$，表示前面$i-1$列已经摆好，且第$i$列状态为$state$的情况下，摆放得最多的积木数量。很显然，答案就是$max_{state=0}^{3}dp[n][state]$，或者$dp[n+1][0]$（可以省去遍历）。

状态转移

在第$i$列有空的格子时当前列可以摆放积木，否则只能进行如下的状态转移

$dp[i][state]=dp[i-1][state]$，（$state \in [0,3]$）。

如果第$i$列全空，有如下情况：

1. 第$i-1$列有空的行，说明积木在横向的凸起可以朝左，此时有状态转移方程$dp[i][3]=max_{state=0}^{2}dp[i-1][state]+1$，注意此时还有$dp[i+1][0]=dp[i][3]$成立。
2. 第$i+1$列有空的行，说明积木在横向的凸起可以朝右，此时如果第$i+1$列上面那一行被占据，则只能放置L型的积木，有状态转移方程$dp[i+1][3]=max_{state=0}^{3}dp[i-1][state]+1$；此时如果第$i+1$列全空，那放置L型的积木就会使得第$i+1$列只有下面那一行的格子被占据，为状态$2$，状态转移方程为$dp[i+1][2]=max_{state=0}^{3}dp[i-1][state]+1$，而放置倒L型积木就会使得第$i+1$列只有上面那一行的格子被占据，为状态$1$，状态转移方程为$dp[i+1][1]=max_{state=0}^{3}dp[i-1][state]+1$。

如果第$i$列上面的格子被占据，有如下情况：

1. 在第$i-1$列全空的情况下，可以在第$i-1$列放一个L型积木，使得第$i-1$列和第$i$列都变成状态$3$。状态转移方程为$dp[i + 1][0] = dp[i][3] = dp[i - 1][0] + 1$。
2. 在第$i+1$列全空的情况下，可以在第$i+1$列放一个反L型积木，使得第$i$列和第$i+1$列都变成状态$3$。状态转移方程为$dp[i + 1][3] = dp[i - 1][0] + 1$。

同理，如果第$i$列下面的格子被占据，有如下情况：

1. 在第$i-1$列全空的情况下，可以在第$i-1$列放一个倒L型积木，使得第$i-1$列和第$i$列都变成状态$3$。状态转移方程为$dp[i + 1][0] = dp[i][3] = dp[i - 1][0] + 1$。
2. 在第$i+1$列全空的情况下，可以在第$i+1$列放一个7型积木，使得第$i$列和第$i+1$列都变成状态$3$。状态转移方程为$dp[i + 1][3] = dp[i - 1][0] + 1$。

以上的状态转移都选择最大值进行转移。

复杂度分析

时间复杂度

状态数量为$4n$量级，单次转移的时间复杂度为$O(1)$，因此算法整体的时间复杂度为$O(n)$。

空间复杂度

空间消耗的瓶颈就是$4 \times n$的DP数组，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
char s[2][N];
int dp[N][4];

int main() {
    scanf("%s", s[0] + 1);
    scanf("%s", s[1] + 1);
    int n = strlen(s[0] + 1);
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        for(int mask = 0; mask <= 3; mask++) {
            dp[i][mask] = max(dp[i][mask], dp[i - 1][mask]);
            dp[i + 1][0] = max(dp[i][mask], dp[i + 1][0]);
        }
        if(s[0][i] == '0' && s[1][i] == '0') {
            // 放朝左的块
            if(i > 1 && s[0][i - 1] == '0' || s[1][i - 1] == '0') {
                for(int mask = 0; mask <= 2; mask++) {
                    dp[i + 1][0] = dp[i][3] = max(dp[i][3], dp[i - 1][mask] + 1);
                }
            }
            // 放朝右的块
            if(i < n && s[0][i + 1] == '0') {
                for(int mask = 0; mask <= 3; mask++) {
                    if(s[1][i + 1] == '0') {
                        dp[i + 1][1] = max(dp[i - 1][mask] + 1, dp[i + 1][1]);
                    }else {
                        dp[i + 1][3] = max(dp[i - 1][mask] + 1, dp[i + 1][3]);
                    }
                }
            }
            if(i < n && s[1][i + 1] == '0') {
                for(int mask = 0; mask <= 3; mask++) {
                    if(s[0][i + 1] == '0') {
                        dp[i + 1][2] = max(dp[i - 1][mask] + 1, dp[i + 1][2]);
                    }else {
                        dp[i + 1][3] = max(dp[i - 1][mask] + 1, dp[i + 1][3]);
                    }
                }
            }
        }else if(s[0][i] == '0' || s[1][i] == '0') {
            // 放朝左的块
            if(i > 1 && s[0][i - 1] == '0' && s[1][i - 1] == '0') {
                dp[i + 1][0] = dp[i][3] = dp[i - 1][0] + 1;
            }
            // 放朝右的块
            if(i < n && s[0][i + 1] == '0' && s[1][i + 1] == '0') {
                dp[i + 1][3] = dp[i - 1][0] + 1;
            }
        }
    }
    printf("%d\n", dp[n + 1][0]);
    return 0;
}