P2039 [AHOI2009]跳棋

    • 54通过
    • 173提交
  • 题目提供者 w 站长团
  • 评测方式 云端评测
  • 标签 各省省选 2009 安徽 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    在一个1行N列(N是奇数)的棋盘上,有K个格子是红色的。这种情况下,你有一个跳棋在最左端的格子上。你的目标是将它移动到最右边的格子,在开始移动之间,你可以在棋盘的任意空位上放棋子。在游戏开始后 你只可以随时在一个红色格子上放棋子。棋子的移动规则是:每次只可以选择一个棋子,跳过与之相邻的棋子走到后面的空格上,被它跳过的棋子被吃掉,即从棋盘上移走,如相邻棋子的另一侧有棋子,则不能跳。

    请回答以下两个问题:

    1:移动开始前至少要放多少棋子才能完成任务。

    2:如果要使开始前放的棋子数要求尽量少,那么在移动过程中最少需要放多少个棋子才能完成任务。

    关于规则的补充说明:

    1:只能往空位上放棋子,不管是移动开始前还是移动过程中。

    2:移动前棋盘最左端的那个原始棋子绝对不能被吃掉.

    输入输出格式

    输入格式:

    第一行一个正奇数N.

    第二行有N个整数,如果第i个整数是1,说明第i个格子是红棋,否则为白棋.

    数字间用空格分开

    输出格式:

    两个数字分别代表第一问和第二问的结果.

    输入输出样例

    输入样例#1: 复制
    5
    0 0 0 1 0
    
    
    输出样例#1: 复制
    1
    1

    说明

    在游戏开始前,可以在第二个格子上放上一个棋子,游戏开始后可用最左边的棋子吃掉它,从而移动到第三格。然后由于第四格是个红色的格子,在游戏中可以在那放一个棋子,然后用已经移动第三格的棋子把它吃掉,从而达到终点。

    100%的数据中,N< = 1000,输出中的数字不超过10^ 15

    30%的数据中,N< = 20

    Source: [Ahoi2009] checker

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