原题链接：https://www.acwing.com/problem/content/5475/
题目描述：
我们要在一个 2×n 大小的方格矩阵上铺瓷砖。
每个方格要么是空的（用 0 表示），要么是已经铺上瓷砖的（用 1 表示）。
现在，给定你无限多个占据三个方格的 L 形瓷砖，瓷砖在铺放时可以旋转 90,180,270 度，即它可以有以下四种形态：
瓷砖之间不能有任何重叠部分。
请你计算，最多可以在给定方格矩阵上同时铺放多少块这种 L 形瓷砖。
输入输出描述：
输入格式
共两行，每行包含一个长度为 n 的由 0 和 1 构成的字符串，表示给定的 2×n 方格矩阵。
注意，n 的具体大小并未直接给出，其取值范围在数据范围栏。
输出格式
一个整数，表示可以同时铺放的 L 形瓷砖的最大数量。
数据范围
前 3 个测试点满足 1≤n≤12
所有测试点满足 1≤n≤100
输入样例1：
00
00
输出样例1：
1
输入样例2：
00100101110
01110100100
输出样例2：
4
输入样例3：
01010
01010
输出样例3：
0解题思路：
这个题目和蒙德里安的梦想那个题非常像，最无脑的做法就是状态压缩dp，但是这个题目通过分析还可以得到一种贪心的做法，首先我们可以发现填入的四种图形，都会存在占据某一列俩个格子的情况，占据完这一列之后，还要占据一个格子，那一个格子可以放在当前这一列左边，也可以放在当前这一列右边，我们从前往后填充图形，那么放在左边肯定比放在右边更优，因为放在左边不会对右边后面的填充造成影响，后面有可能填充更多的图形，所以我们能填充左边时，优先考虑填充左边，左边填充不了再考虑右边，右边那一列的俩个格子，如果只有一个格子可以用，那么直接填充那个格子即可，因为这个格子优先贡献给前边，那么肯定会更优，如果俩个格子都可以填充，那么那么随便选择一个格子填充即可，拿一个格子贡献给前边，肯定也会更优，为了方便处理，我们将第0列和第n+1列都设置为1表示不可填充，那么我们就可以得到一个结论。
结论：只有当当前列有俩个空格子时，才能考虑填充，当当前这一列左边有空格时优先填充左边，否则再看右边是否有空格，右边又空格那么也一定要填充右边。
时间复杂度：枚举每一列，所以时间复杂度为O(n)，还是一个大小为8的常数
空间复杂度：O(n)，还有一个大小为2的常数。
cpp代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int n;
char g[2][N];
int main()
{
for(int i=0;i<2;i++)scanf("%s",g[i]+1);
n=strlen(g[0]+1);
g[0][0]=g[1][0]=g[0][n+1]=g[1][n+1]='1'; //最左边一列和最右边一列都设置为1，表示不可填充，方便处理，减少特判
int res=0;
for(int i=1;i<=n;i++)
{
int dx[4]={0,1,0,1},dy[4]={i-1,i-1,i+1,i+1}; //这样设置，优先枚举左边俩个格子，然后才枚举右边俩个格子
if(g[0][i]=='0' && g[1][i]=='0')
{
for(int j=0;j<4;j++)
{
int x=dx[j],y=dy[j];
if(g[x][y]=='0') //找到一个可以填充的位置,把这个位置填充为1,同时答案加1
{
res++;
g[0][i]=g[1][i]=g[x][y]='1';
break;
}
}
}
}
cout<<res<<endl;
return 0;
}
