SCI2005扫雷

题意：
那是在一个n×m的矩阵里面有一些雷，要你根据一些信息找出雷来。这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图：

由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

解题思路：
如果是dp的话，需要设置一个状态能同时表示3个位置，也就是dp[i][a][b][c]，a、b、c的状态分别表示i-1、i、i+1行有没有雷。根据经验只需要表示i和i+1行的状态就可以了。
于是就分类讨论转移方程

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
void read(int& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int mod=1e9+7;
const int maxn = 1e5+7;

int n;
LL dp[maxn][2][2];
int a[maxn],b[maxn];//b代表实际上有没有雷

int main(){
    read(n);
    fo(i,1,n) read(a[i]);
    dp[0][0][1]=dp[0][0][0]=1;

    fo(i,1,n){
        if(a[i]==0){
            dp[i][0][0]+=dp[i-1][0][0];
        }
        else if(a[i]==1){
            dp[i][0][0]+=dp[i-1][1][0];//b[i-1]=1
            dp[i][1][0]+=dp[i-1][0][1];//b[i]=1
            dp[i][0][1]+=dp[i-1][0][0];//b[i+1]=1
        }
        else if(a[i]==2){
            dp[i][1][1]+=dp[i-1][0][1];//b[i-1]=0
            dp[i][0][1]+=dp[i-1][1][0];//b[i]=0
            dp[i][1][0]+=dp[i-1][1][1];//b[i+1]=0
        }
        else{
            dp[i][1][1]+=dp[i-1][1][1];
        }
    }
    LL ans=0;
    fo(i,0,1) ans+=dp[n][i][0];
    printf("%lld\n",ans);
    return 0;
}