欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CodeForces - 991D Bishwock (DP)

程序员文章站 2022-07-01 10:55:37
...

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          0    6
思路:
第一次自己推出这样的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]);
}

CodeForces - 991D Bishwock (DP)