[SCOI2005]扫雷MINE

题意:给定一个扫雷得序列,来猜另一个序列,并且当前序列没有雷,比如样例:
1 1 或者 1 1
0 雷 ||||| 雷 0
然后题目要求是问,一共有可能有多少种情况是构成另一个序列
题解:
f[i][0/1][0/1][0/1]
对于第i个位置而言,第i-1,i,i+1个位置是否有雷
所以得到
当a[i]=0时:

当a[i]=1时:

当a[i]=2时:

当a[i]=3时:

最后输出最后一位a[i]为几时所对应得答案

# include<iostream>
using namespace std;
int n,tot;
int a[10001];
int f[10001][2][2][2];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>a[i];
    f[0][0][0][0]=f[0][0][0][1]=1;
    for(int i=1;i<=n;i++)
      {
          if(!a[i]) f[i][0][0][0]=f[i-1][0][0][0]+f[i-1][1][0][0];
          if(a[i]==1)
          {
              f[i][1][0][0]=f[i-1][0][1][0]+f[i-1][1][1][0];
              f[i][0][1][0]=f[i-1][0][0][1]+f[i-1][1][0][1];
              f[i][0][0][1]=f[i-1][0][0][0]+f[i-1][1][0][0];
        }
        if(a[i]==2)
        {
            f[i][1][1][0]=f[i-1][0][1][1]+f[i-1][1][1][1];
            f[i][1][0][1]=f[i-1][0][1][0]+f[i-1][1][1][0];
            f[i][0][1][1]=f[i-1][0][0][1]+f[i-1][1][0][1];
        }
        if(a[i]==3) f[i][1][1][1]=f[i-1][0][1][1]+f[i-1][1][1][1];
      }
    if(!a[n]) tot=f[n][0][0][0];
    if(a[n]==1) tot=f[n][1][0][0]+f[n][0][1][0];
    if(a[n]==2) tot=f[n][1][1][0];
    cout<<tot;
    return 0;
}

然后还可以压缩掉一维,压缩掉第i-1维,比如我们要计算第i位数,那么第i-2位对于结果时没有关系的
解释:对于第5位而言时4,5,6,同样的几位对于第4位而言是3,4,5,而第3位影响不到第5位
当a[i]=0时:

当a[i]=1时:

当a[i]=2时:

当a[i]=3时:

最后输出: