Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

12/27
14:49
模拟

[bzoj 1088] SCOI2005 扫雷Mine

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

2
1 1

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

因为只要确定了f[i-1]和f[i],就可以通过a[i]得出f[i+1]的值,所以只要确定了f[1]和f[2],整个序列也就确定了,最后判断一下是否可行即可。

c++:

pascal:

 

[bzoj 1088] SCOI2005 扫雷Mine