扫雷MINE

//扫雷MINE
//枚举优化，注意到只要确定了第一个空的状态，第二空的状态也是定的，以此类推，只要看最后一个空是否合理就行 
#include <iostream> 
#include <cstring>
#include <cstdio>
using namespace std;
int arr[10005];//存输入的数据 
int res[10005];//存方案 
int n,cnt=0;//计数多少种方案 
bool check()//通过arr最后一个数，检查扫雷的第一列是否合理 
{
    if(arr[n]-res[n]-res[n-1]==0)    return true;
    else return false ;
}
void dfs(int pos)//用了搜索的板子写枚举 
{
    int i,j,k;
    if(pos==n+1)//当最后一个空填完后，检查 
    {
    if(check()) cnt++;//如果合理，计数+1 
    return ;
    }
    res[pos]=arr[pos-1]-res[pos-1]-res[pos-2];//每个位置是否有雷，等于右上角的数字减去上面两个空的雷数 
    if(res[pos]<0)    return; //如果出现负数，直接排除 
    dfs(pos+1);//搜索下一位 
}
int main()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++)    cin>>arr[i];
    res[1]=0;dfs(2);//若第一个位置无雷 
    memset(res,0,sizeof(res));//清空记录 
    res[1]=1;dfs(2);//若第二个位置有雷 
    cout<<cnt<<endl;

}