[SCOI2005]扫雷MINE

题目链接：https://ac.nowcoder.com/acm/problem/20241

这个题是可以用dp写的（虽然我dp贼菜，写这玩意写的我头大）。不过这个题还是蛮好懂的（看了大佬题解以后）。

每个位置只有有雷或者没雷两种情况，我们可以用0表示没有雷，1表示有雷。我们用x数组来存数量，y数组来存当前位置有没有雷，根据扫雷的规则，我们可以得到，x[i]=y[i-1]+y[i]+y[i+1]，转换一下可以得到y[i+1]=x[i]-y[i]-y[i-1]。因此我们就得到了状态转移方程，我们就可以用它来解题啦。具体看代码注释。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int x[100005]={0};
int y[100005]={0};
int ans=0;
int n;
int solve()
{
    for(int i=2;i<n;i++)
    {
        y[i+1]=x[i]-y[i]-y[i-1];
        if(y[i+1]<0||y[i+1]>1) return 0;//当前位置只能为0或者为1哦 
    }
    if(y[n]+y[n-1]!=x[n]) return 0;//最后一个位置判断一下 
    return 1;
}
int main()
{
    cin>>n;
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        if(x[i]>3) flag=1;//大于三个当然不可能啦 
    }
    if(x[1]>2||x[n]>2||flag==1)//第一个和最后一个最多只能有两个啦 
    {
        cout<<0;
        return 0;
    }
    if(x[1]==2)//第一个和第二个位置都有雷 然后解题 
    {
        y[1]=1;
        y[2]=1;
        ans+=solve();
    }
    else if(x[1]==0)//第一个和第二个位置没有雷 
    {
        y[1]=0;
        y[2]=0;
        ans+=solve();
    }
    else if(x[1]==1)//有两种情况，搞一下就可以了 
    {
        y[1]=1;
        ans+=solve();
        memset(y,0,sizeof(y));
        y[2]=1;
        ans+=solve();
    }
    cout<<ans;//完事 
}