P2327 [SCOI2005]扫雷

2018-06-17 22:17:06来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

输入输出格式

输入格式:

 

第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<= N <= 10000)

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
2
1  1
输出样例#1:
2

 ‘

我们用dp[i]表示左边的第i个位置是否有雷,

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #include<cstdlib>
 8 using namespace std;
 9 const int MAXN=10001;
10 void read(int &n)
11 {
12     char c='+';int x=0,flag=1;
13     while(c<'0'||c>'9')
14     {c=getchar();if(c=='-')flag=-1;}
15     while(c>='0'&&c<='9')
16     {x=x*10+c-48;c=getchar();}
17     n=(x*flag);
18 }
19 int k=1,m,n;
20 int i,j;
21 int a[MAXN],dp[MAXN];
22 int main()
23 {
24     read(n);
25     for(i=1;i<=n;i++)
26         read(a[i]);
27     for(i=2;i<=n+1;i++)
28     {
29         dp[i]=a[i-1]-dp[i-1]-dp[i-2];
30         if(dp[i]<0||dp[i]>1)
31         {
32             k=0;
33             break;
34         }
35     }
36     if(dp[n+1]!=0)k=0;
37     m+=k;
38     memset(dp,0,sizeof(dp));
39     k=1;
40     dp[1]=1;
41     for(i=2;i<=n+1;i++)
42     {
43         dp[i]=a[i-1]-dp[i-1]-dp[i-2];
44         if(dp[i]<0||dp[i]>1)
45         {
46             k=0;
47             break;
48         }
49     }
50     if(dp[n+1]!=0)k=0;
51     m+=k;
52     printf("%d\n",m);
53     return 0;
54 } 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1629 邮递员送信(未完成)

下一篇:POJ 2001 Shortest Prefixes