P2327 [SCOI2005]扫雷

    • 1.3K通过
    • 3.2K提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 各省省选 2005 四川
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    相信大家都玩过扫雷的游戏。那是在一个 $n\times m$ 的矩阵里面有一些雷,要你根据一些信息找出雷来。万圣节到了,“余”人国流行起了一种简单的扫雷游戏,这个游戏规则和扫雷一样,如果某个格子没有雷,那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是 $n\times 2$ 的,第一列里面某些格子是雷,而第二列没有雷,如下图:

    由于第一列的雷可能有多种方案满足第二列的数的限制,你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    2
    1  1
    输出样例#1: 复制
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。