CodeForces - 991D Bishwock （DP）

CodeForces - 991D Bishwock （DP）

题目链接
题目大意：在一个2 * n的方格(有些格子被占据)里面放4种形态的小方格，这四种形态分别对应四个小方格形成的正方形缺一个角。用x表示小方格，.表示空白，这四个形态分别是
XX XX .X X.
X. .X XX XX
然后问你最多能放多少个？

input
00　　　00X00X0XXX0　　　0X0X0　　　000000
00　　　0XXX0X00X00　　　0X0X0　　　000000
1　　　 4　　　　　　　　　　０　　　　６
思路：
第一次自己推出这样的dp，真的好开心！！！
dp[i][j] 表示第一行选前i个，第二行选前j个组成的方格最多可以放多少个。
详情见代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e2 + 100;
int dp[maxn][maxn];
char str[3][maxn];

int main()
{
    scanf("%s", str[0] + 1);
    scanf("%s", str[1] + 1);

    int len = strlen(str[1] + 1);

    for(int i = 1; i <= len; i++)
    {
        for(int j = 1; j <= len; j++)
        {
            dp[i][j] = dp[i][j - 1]; //不管str[1][j]是不是0，都成立
            //str[1][j] 是X时新来的位置对前一种状态不产生任何影响

            //新来的位置如果是空的，如果要用它的话，有四种放法，不用的话依旧是dp[i][j - 1]
            //四种做法见图 红点表示j的位置 
            if(str[1][j] == '0')
            {
                if(j - 2 >= 0 && str[0][j - 1] == '0' && str[1][j - 1] == '0') //对应图1，对i的位置没有要求
                {
                    dp[i][j] = max(dp[i][j], dp[j - 2][j - 2] + 1);
                }
                if(i >= j)
                {
                    if(j - 2 >= 0 && str[0][j] == '0' && str[1][j - 1] == '0') //图2
                        dp[i][j] = max(dp[i][j], dp[j - 1][j - 2] + 1);
                    if(j - 2 >= 0 && str[0][j] == '0' && str[0][j - 1] == '0') //图3
                        dp[i][j] = max(dp[i][j], dp[j - 2][j - 1] + 1);

                }
                if(i >= j + 1) 
                {
                    if(j - 1 >= 0 && str[0][j] == '0' && str[0][j + 1] == '0') //图4
                        dp[i][j] = max(dp[i][j], dp[j - 1][j - 1] + 1);
                }
            }
        }
    }
    printf("%d\n", dp[len][len]);
}