bzoj 1088 [SCOI2005] 扫雷

SCOI2005 扫雷

一道很有趣的(水)题

“这道题有四种解法，你知道么”

给你矩阵的第二列的数字，求出第一列雷有多少种可能的摆法。

不懂扫雷规则的自行按win+R然后输入winmine

思考过后我想到了一种拙劣的DP写法，

四维 F[i][][][] i代表到了第几个格子，后面三维用 0和1表示这个格子旁边雷的情况，分别是左上左左下

简单易懂(十分恶心)的代码

#include<bits/stdc++.h>

using namespace std;

int N,a[],f[][][][];

int main()

{

    ios::sync_with_stdio(false);

    cin>>N;

    for(int i=;i<=N;i++)cin>>a[i];

    if        (a[]==)f[][][][]=;

    else if    (a[]==)f[][][][]=,f[][][][]=;

    else if    (a[]==)f[][][][]=;

    for(int i=;i<=N-;i++)

    {

        if        (a[i]==)

            f[i][][][]=f[i-][][][]+f[i-][][][];

        else if    (a[i]==)

            f[i][][][]=f[i-][][][]+f[i-][][][],

            f[i][][][]=f[i-][][][]+f[i-][][][],

            f[i][][][]=f[i-][][][]+f[i-][][][];

        else if    (a[i]==)

            f[i][][][]=f[i-][][][]+f[i-][][][],

            f[i][][][]=f[i-][][][]+f[i-][][][],

            f[i][][][]=f[i-][][][]+f[i-][][][];

        else if    (a[i]==)

            f[i][][][]=f[i-][][][]+f[i-][][][];

    }

    if        (a[N]==) cout<<f[N-][][][]+f[N-][][][];

    else if    (a[N]==) cout<<f[N-][][][]+f[N-][][][]+f[N-][][][]+f[N-][][][];

    else if    (a[N]==) cout<<f[N-][][][]+f[N-][][][];

    return ;

}

就是枚举出了所有的情况，暴力转移。 (手边要有个画图板边写边画别漏情况)

美其名曰DP

当时代码写得十分顺，一遍过编译，一遍AC

实际上，没这么复杂。

现在我们可以思考一下，第二列数字都已知，如果你知道了第一列的前两个格子是否有雷，那么我们就可以把所有的都推出来了

b[i]=a[i-1]-b[i-1]-b[i-2] (b[i]是格子i的雷，a[i]是第二列的数字)

所以只要枚举前两个格子的雷就可以了。

这题答案只有 0，1，2；

超短代码↓

#include<bits/stdc++.h>

using namespace std;

int N,a[],ans;

void Work(int x,int y)

{

    int b[];

    b[]=x,b[]=y;

    for(int i=;i<=N+;i++)

        b[i]=a[i-]-b[i-]-b[i-];

    if(b[N+]==)ans++;

}

int main()

{

    ios::sync_with_stdio(false);

    cin>>N;

    for(int i=;i<=N;i++)cin>>a[i];

    if        (a[]==)Work(,),Work(,);

    else if    (a[]==)Work(,);

    else if (a[]==)Work(,);

    cout<<ans<<endl;

    return ;

}

巴特西

bzoj 1088 [SCOI2005] 扫雷

SCOI2005 扫雷

最新文章

热门文章