Luogu P2327 [SCOI2005]扫雷

YorkWu

March 11, 2019

1196 views

No comments

631 words

OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P2327 "题目链接")

#### 思路：

*   这道题一开始想的状态是$f(i,j)$表示第i个位置放与不放炸弹（用j表示），后来怎么也写不对代码:sweat:，所以我看了眼题解，少了一维。
*   咳咳，正解：
*   先设计状态，$f(i,j,k)$表示第i个位置放不放炸弹和下一位放不放炸弹（分别用j，k表示），这样就可以推出转移的方法。
    1.  当第i位数字为0时，那直接从$f(i-1,0,0)$转移过来。
    2.  当为1时，就有分别把炸弹放到3个格子当中的3种方法。
    3.  当为2,3时，同理。

> P.S. 题解上说答案只能是大于0，小于2，貌似是的，但是为什么？求大佬解释qwq。

#### 代码如下：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    int f[10009][2][2],a[10009],n;
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        f[0][0][0]=f[0][0][1]=1;//第0个位置一定不选，下个位置有选和不选两种情况。 
        for(int i=1;i<=n;i++){
            if(a[i]==0)//如果这个位置为0，那这个位置和上下位置均不选。 
                f[i][0][0]+=f[i-1][0][0];
            if(a[i]==1)//如果为1，那可以这个位置和上下两个位置任意一个选。下方同理。 
                f[i][1][0]+=f[i-1][0][1],f[i][0][1]+=f[i-1][0][0],f[i][0][0]+=f[i-1][1][0];
            if(a[i]==2)
                f[i][1][0]+=f[i-1][1][1],f[i][0][1]+=f[i-1][1][0],f[i][1][1]+=f[i-1][0][1];
            if(a[i]==3)
                f[i][1][1]+=f[i-1][1][1];
        }
        cout<<f[n][1][0]+f[n][0][0];//在第n个选与不选的结果相加即为ans。 
        return 0;
    }
```

Last modification：March 14, 2020