【BZOJ 1088】【SCOI 2005】掃雷mine

2019-11-08 02:09:37

字體：大中小

供稿：網(wǎng)友

Description

相信大家都玩過(guò)掃雷的游戲。那是在一個(gè)n*m的矩陣?yán)锩嬗幸恍├祝愀鶕?jù)一些信息找出雷來(lái)。萬(wàn)圣節(jié)到了，“余”人國(guó)流行起了一種簡(jiǎn)單的掃雷游戲，這個(gè)游戲規(guī)則和掃雷一樣，如果某個(gè)格子沒(méi)有雷，那么它里面的數(shù)字表示和它8連通的格子里面雷的數(shù)目。現(xiàn)在棋盤是n×2的，第一列里面某些格子是雷，而第二列沒(méi)有雷。由于第一列的雷可能有多種方案滿足第二列的數(shù)的限制，你的任務(wù)即根據(jù)第二列的信息確定第一列雷有多少種擺放方案。

Input

第一行為N，第二行有N個(gè)數(shù)，依次為第二列的格子中的數(shù)。（1<= N <= 10000）

Output

一個(gè)數(shù)，即第一列中雷的擺放方案數(shù)。

Sample Input

2 1 1

Sample Output

題解

由于每個(gè)格子可由前兩個(gè)推出來(lái)，所以簡(jiǎn)單討論第一個(gè)格子和第二個(gè)格子即可，并判斷符不符合。

代碼

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 10010int a[N],f[N];int n,ans;bool jud(){ for(int i = 2;i <= n;i++) { f[i+1] = a[i] - f[i] - f[i-1]; if(f[i+1] < 0) return 0; } if(a[n] != f[n] + f[n-1]) return 0; return 1;}int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); ans = 0; if(a[1] == 0) ans += jud(); else if(a[1] == 1)//分類討論 { f[1] = 1; ans += jud(); memset(f,0,sizeof(f)); f[2] = 1; ans += jud(); } else { f[1] = f[2] = 1;ans += jud(); }