P2327 [SCOI2005]扫雷

https://www.luogu.org/problem/show?pid=2327

题目描述

输入输出格式

输入格式：

第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

输出格式：

一个数，即第一列中雷的摆放方案数。

输入输出样例

输入样例#1：

2

1  1

输出样例#1：

算法1：

枚举左边每个位置是否有雷，复杂度O(2^n*n)。

算法2：

我们发现，当前两个位置确定时，后面的位置也就可以推出来了。

于是我们可以只枚举前两位。

复杂度O(n)

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

int n,num[],a[];

bool mine[],flag;

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&num[i]);

    if(num[]==){printf("");return ;}

    if(num[]==){

        mine[]=;mine[]=;

        a[]=;

        for(int i=;i<=n-;i++){

            for(int j=i-;j<=i+;j++)a[i]+=mine[j];

            if(a[i]==num[i])mine[i+]=;

            else if(a[i]==num[i]-)a[i]++,mine[i+]=;

            else {flag=;break;}

        }

        if(flag==){printf("");return ;}

        a[n]+=mine[n-];a[n]+=mine[n];

        if(a[n]==num[n]){printf("");return ;}

        else{printf("");return ;}

    }

    if(num[]==){

        int ans=;

        mine[]=;mine[]=;

        a[]=;

        for(int i=;i<=n-;i++){

            for(int j=i-;j<=i+;j++)a[i]+=mine[j];

            if(a[i]==num[i])mine[i+]=;

            else if(a[i]==num[i]-)a[i]++,mine[i+]=;

            else {flag=;break;}

        }

        if(flag!=){a[n]+=mine[n-];a[n]+=mine[n];if(a[n]==num[n])ans++;}

        memset(mine,,sizeof(mine));

        memset(a,,sizeof(a));

        mine[]=;mine[]=;

        a[]=;

        for(int i=;i<=n-;i++){

            for(int j=i-;j<=i+;j++)a[i]+=mine[j];

            if(a[i]==num[i])mine[i+]=;

            else if(a[i]==num[i]-)a[i]++,mine[i+]=;

            else {flag=;break;}

        }

        if(flag!=){a[n]+=mine[n-];a[n]+=mine[n];if(a[n]==num[n])ans++;}

        printf("%d",ans);return ;

    }

    if(num[]==){

        mine[]=;mine[]=;

        a[]=;

        for(int i=;i<=n-;i++){

            for(int j=i-;j<=i+;j++)a[i]+=mine[j];

            if(a[i]==num[i])mine[i+]=;

            else if(a[i]==num[i]-)a[i]++,mine[i+]=;

            else {flag=;break;}

        }

        if(flag==){printf("");return ;}

        a[n]+=mine[n-];a[n]+=mine[n];

        if(a[n]==num[n]){printf("");return ;}

        else{printf("");return ;}

    }

}

巴特西

洛谷 P2327 [SCOI2005]扫雷

P2327 [SCOI2005]扫雷

题目描述

输入输出格式

输入输出样例

最新文章

热门文章