【题目链接】:http://codeforces.com/problemset/problem/404/D

【题意】



让你玩一个1维的扫雷游戏;

游戏的描述由数字0..2以及符号*表示;

分别表示这个格子的相邻的两个格子里面有几个炸弹;以及炸弹;

然后挖一些空;

问你有多少种填满的方案;

【题解】



dp[i][1] 表示前i个位置,第i个位置放0的方案数

dp[i][2] 表示钱i个位置,第i个位置放1,前一位没炸弹的方案数

dp[i][3] …..放1,前一位有炸弹…..

dp[i][4] …..放2….

dp[i][5] ….放炸弹….

根据每一位是什么进行转移就可以了;

转移也很容易想的;

然后初值根据s[1]的值来置;



【Number Of WA】



3



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("D:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1e6+100;

const int MOD = 1e9+7;

char s[N];

int dp[N][6],ans,n;

inline void add(int &a,int &b){

    a+=b;

    if (a>=MOD) a-=MOD;

}

int main(){

    //Open();

    scanf("%s",s+1);

    if (s[1]=='0'){

        dp[1][1] = 1;

    }else if (s[1]=='1'){

        dp[1][2] = 1;

    }else if (s[1]=='2'){

        //dp[1][4] = 1;

    }else if (s[1]=='*'){

        dp[1][5] = 1;

    }else{

        dp[1][1] = dp[1][2] = dp[1][5] = 1;

    }

    n = (int) strlen(s+1);

    //dp[i][1] 放0

//dp[i][2] 放1,前一位没炸弹

//dp[i][3] 放1,前一位有炸弹

//dp[i][4] 放2

//dp[i][5] 放炸弹

    rep1(i,2,n){

        if (s[i]=='0'){

            add(dp[i][1],dp[i-1][1]);

            add(dp[i][1],dp[i-1][3]);

        }else if (s[i]=='1'){

            add(dp[i][2],dp[i-1][1]);

            add(dp[i][2],dp[i-1][3]);

            add(dp[i][3],dp[i-1][5]);

        }else if (s[i]=='2'){

            add(dp[i][4],dp[i-1][5]);

        }else if (s[i]=='*'){

            add(dp[i][5],dp[i-1][2]);

            add(dp[i][5],dp[i-1][4]);

            add(dp[i][5],dp[i-1][5]);

        }else if (s[i]=='?'){

            add(dp[i][1],dp[i-1][1]);

            add(dp[i][1],dp[i-1][3]);

            add(dp[i][2],dp[i-1][1]);

            add(dp[i][2],dp[i-1][3]);

            add(dp[i][3],dp[i-1][5]);

            add(dp[i][4],dp[i-1][5]);

            add(dp[i][5],dp[i-1][2]);

            add(dp[i][5],dp[i-1][4]);

            add(dp[i][5],dp[i-1][5]);

        }

    }

    add(ans,dp[n][1]),add(ans,dp[n][3]),add(ans,dp[n][5]);

    cout << ans << endl;

    return 0;

}