• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

牛客每日一题SCI2005扫雷

admin

11月 28, 2021

这道题可以直接枚举第一个格子状态,之后check即可。因为方案最多只有两种

当然也可以用dp

以下是dp做法:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 10;

int n;
int a[maxn];
int f[maxn][2][2];///当前位置, 当前格子是否摆放,后一个格子是否摆放
///为啥不设前一个格子呢。因为这样的话那么初始化就不是很好表示了。(需要把a[1]拉出来分类初始化

int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
    }

    f[0][0][1]=1;f[0][0][0]=1;
    for (int i = 1; i <= n; ++ i) {
        if (a[i] == 0) {
            f[i][0][0] += f[i-1][0][0];
        }
        else if (a[i] == 1) {
            f[i][1][0] += f[i-1][0][1];
            f[i][0][1] += f[i-1][0][0];
            f[i][0][0] += f[i-1][1][0];
        }
        else if (a[i] == 2) {
            f[i][1][0] += f[i-1][1][1];
            f[i][0][1] += f[i-1][1][0];
            f[i][1][1] += f[i-1][0][1];
        }
        else if (a[i] == 3){
            f[i][1][1] += f[i-1][1][1];
        }
    }

    cout << f[n][0][0] + f[n][1][0] << endl;
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。