BZOJ 1088 [SCOI2005]扫雷Mine

1088: [SCOI2005]扫雷Mine

Description

　　相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图：由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

Input

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

Output

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

Sample Input

2
1 1

Sample Output

　　这很明显是一道水题。看上去像是DP，但其实如果定了前2位，则可以完全推得n个位置。然后最后判断最后2个位置是否符合要求，hzwer说这是模拟题。

　　然后，当n==1时无需特判，但是存在aa[1]==0的情况（第一次WA了没有考虑到）。

 1 /**************************************************************
 2     Problem: 1088
 3     User: Doggu
 4     Language: C++
 5     Result: Accepted
 6     Time:8 ms
 7     Memory:900 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 template<class T>inline void readin(T &res) {
12     static char ch;T flag=1;
13     while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;
14     res=ch-48;while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;
15 }
16 const int N = 10010;
17 int n, aa[N], bb[N], ans, ok;
18 bool check() {
19     for( int i = 2; i <= n-1; i++ ) {
20         bb[i+1]=aa[i]-bb[i]-bb[i-1];
21         if(bb[i+1]<0||bb[i+1]>1) return 0;
22     }
23     return bb[n-1]+bb[n]==aa[n];
24 }
25 int main() {
26     readin(n);for( int i = 1; i <= n; i++ ) readin(aa[i]);
27     if(n==1||aa[1]==0) ans+=check();
28     else if(aa[1]==1) {
29         bb[1]=0;bb[2]=1;ans+=check();
30         bb[1]=1;bb[2]=0;ans+=check();
31     } else if(aa[1]==2) {
32         bb[1]=1;bb[2]=1;ans+=check();
33     }
34     printf("%d
",ans);
35     return 0;
36 }
37

模拟