洛谷 P2327 [SCOI2005]扫雷

题目传送门

f[i][1/0][1/0]表示到第i列时,第i列是否放,第i-1列是否放的方案数.

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,a[10001],f[10001][2][2];

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n; i++)
        scanf("%d",&a[i]);
    f[1][1][0] = f[1][0][0] = 1;
    for(int i = 2;i <= n; i++) {
        if(a[i-1] == 3) {
            f[i][1][1] = f[i-1][1][1];
            f[i][1][0] = 0;
            f[i][0][1] = 0;
            f[i][0][0] = 0;
        }
        if(a[i-1] == 2) {
            f[i][1][0] = f[i-1][0][1];
            f[i][1][1] = f[i-1][1][0];
            f[i][0][0] = 0;
            f[i][0][1] = f[i-1][1][1];
        }
        if(a[i-1] == 1) {
            f[i][1][0] = f[i-1][0][0];
            f[i][1][1] = 0;
            f[i][0][0] = f[i-1][0][1];
            f[i][0][1] = f[i-1][1][0];
        }
        if(a[i-1] == 0) {
            f[i][1][0] = 0;
            f[i][1][1] = 0;
            f[i][0][1] = 0;
            f[i][0][0] = f[i-1][0][0];
        }
    }
    if(a[n] == 1) printf("%d",f[n][1][0] + f[n][0][1]);
    if(a[n] == 2) printf("%d",f[n][1][1]); 
    if(a[n] == 0) printf("%d",f[n][0][0]);
    return 0;
}