首页 > 代码库 > 洛谷 P2327 [SCOI2005]扫雷
洛谷 P2327 [SCOI2005]扫雷
P2327 [SCOI2005]扫雷
https://www.luogu.org/problem/show?pid=2327
题目描述
输入输出格式
输入格式：
第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）
输出格式：
一个数，即第一列中雷的摆放方案数。
输入输出样例
输入样例#1：
21 1
输出样例#1：
2
算法1：
枚举左边每个位置是否有雷，复杂度O(2^n*n)。
算法2：
我们发现，当前两个位置确定时，后面的位置也就可以推出来了。
于是我们可以只枚举前两位。
复杂度O(n)
#include<iostream>#include<cstring>#include<cstdio>using namespace std;int n,num[10010],a[10010];bool mine[10010],flag;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&num[i]); if(num[1]==3){printf("0");return 0;} if(num[1]==2){ mine[1]=1;mine[2]=1; a[1]=2; for(int i=2;i<=n-1;i++){ for(int j=i-1;j<=i+1;j++)a[i]+=mine[j]; if(a[i]==num[i])mine[i+1]=0; else if(a[i]==num[i]-1)a[i]++,mine[i+1]=1; else {flag=1;break;} } if(flag==1){printf("0");return 0;} a[n]+=mine[n-1];a[n]+=mine[n]; if(a[n]==num[n]){printf("1");return 0;} else{printf("0");return 0;} } if(num[1]==1){ int ans=0; mine[1]=1;mine[2]=0; a[1]=1; for(int i=2;i<=n-1;i++){ for(int j=i-1;j<=i+1;j++)a[i]+=mine[j]; if(a[i]==num[i])mine[i+1]=0; else if(a[i]==num[i]-1)a[i]++,mine[i+1]=1; else {flag=1;break;} } if(flag!=1){a[n]+=mine[n-1];a[n]+=mine[n];if(a[n]==num[n])ans++;} memset(mine,0,sizeof(mine)); memset(a,0,sizeof(a)); mine[1]=0;mine[2]=1; a[1]=1; for(int i=2;i<=n-1;i++){ for(int j=i-1;j<=i+1;j++)a[i]+=mine[j]; if(a[i]==num[i])mine[i+1]=0; else if(a[i]==num[i]-1)a[i]++,mine[i+1]=1; else {flag=1;break;} } if(flag!=1){a[n]+=mine[n-1];a[n]+=mine[n];if(a[n]==num[n])ans++;} printf("%d",ans);return 0; } if(num[1]==0){ mine[1]=0;mine[2]=0; a[1]=0; for(int i=2;i<=n-1;i++){ for(int j=i-1;j<=i+1;j++)a[i]+=mine[j]; if(a[i]==num[i])mine[i+1]=0; else if(a[i]==num[i]-1)a[i]++,mine[i+1]=1; else {flag=1;break;} } if(flag==1){printf("0");return 0;} a[n]+=mine[n-1];a[n]+=mine[n]; if(a[n]==num[n]){printf("1");return 0;} else{printf("0");return 0;} }}
洛谷 P2327 [SCOI2005]扫雷
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。