P2327 [SCOI2005]扫雷

浅浅的花香味﹌ 2022-06-07 14:08 151阅读 0赞

[https://www.luogu.org/problem/show?pid=2327][https_www.luogu.org_problem_show_pid_2327]

借鉴了一位dalao(@xyz32768)(洛谷)的题解  
设一个四维数组f\[i\]\[0/1\]\[0/1\]\[0/1\]，分别表示第i个，i-1个是否有地雷,i个是否有地雷,i+1个是否有地雷。  
当a=0时（如图）  
![a=0][a_0]图1  
此时只有一种情况：  
![这里写图片描述][SouthEast]  
也就是`f[i][0][0][0]=f[i-1][0][0][0]+f[i-1][1][0][0]。`

当a=1时，如下图所示：  
![a=1][a_1]

此时，有三种情况：  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]  
![这里写图片描述][SouthEast 3]  
即:

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]。

其他两种情况详见代码。

边界条件是f\[0\]\[0\]\[0\]\[0\] = f\[0\]\[0\]\[0\]\[1\] =1(这两种情况下都只有一种)

此外，结果取决于最后一个数字。如果该数字为0，说明答案是f\[n\]\[0\]\[0\]\[0\]；为1，则为f\[n\]\[1\]\[0\]\[0\]与f\[n\]\[0\]\[1\]\[0\]之和。其他两种情况见代码。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    
    using namespace std;
    
    int f[10005][2][2][2];
    
    inline int read(){
        int res = 1,x = 0;
        char ch = 0;
        while(ch<'0'||ch>'9'){
            if (ch=='-')
                res = -1;
            ch = getchar();
        }
        while(ch>='0'&&ch<='9'){
            x = (x<<3) + (x<<1) + ch - 48;
            ch = getchar();
        }
        return x*res;
    }
    
    int main(){
        int  n = read();
        int a;
        f[0][0][0][0] = f[0][0][0][1] = 1;
        for (int i =1;i<=n;i++){
            a = read();
            switch(a){
                case 0:
                    f[i][0][0][0] = f[i-1][0][0][0] + f[i-1][1][0][0];
                    break;
                case 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];
                    break;
                case 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];
                    break;
                case 3:
                    f[i][1][1][1] = f[i-1][0][1][1] + f[i-1][1][1][1];
                    break;
            }
        }
        int ans;
        if (a == 0) ans = f[n][0][0][0];
        if (a == 1) ans = f[n][1][0][0] + f[n][0][1][0];
        if (a == 2) ans = f[n][1][1][0];
        if (a == 3) ans = 0;
        cout<<ans<<endl;
        return 0;   
    }

[https_www.luogu.org_problem_show_pid_2327]: https://www.luogu.org/problem/show?pid=2327
[a_0]: /images/20220607/9a42b250f5174e0a8426bef770ad7c86.png
[SouthEast]: /images/20220607/feb0766dcc3f4447854efc274d8e6957.png
[a_1]: /images/20220607/d159aa70ed68426380ebaa5a12982ecc.png
[SouthEast 1]: /images/20220607/fc06b96dbb31450e8ee54002334d0332.png
[SouthEast 2]: /images/20220607/7e1d8483f26e4105a33aab5c9fd9f79d.png
[SouthEast 3]: /images/20220607/e81ecea4fbf54d0d9dbd56ec9133103c.png