P1805 关灯

    • 34通过
    • 136提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 线性递推,递推式 递推 高精 NOI导刊
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    在某条道路上,有n盏灯排成一排,它们有的是开着的,有的是关着的。

    由于天马上就要亮了,上级给了你一个任务:把所有的灯都关掉。

    只不过,这些灯都比较智能,不会被轻易关掉。它们的开或关遵循如下规则:

    • 每一步只能开或关一盏灯

    • 编号为1 的灯可以随意开或关

    • 如果编号为1,…,k-1 的灯都关上了了,并且编号为k 的灯在开着,我们可

    以随意开或关第k+1 盏灯

    在关灯之前,请你计算:至少要多少步才能关上所有灯?

    输入输出格式

    输入格式:

    * 第 1 行: 有一个整数n,表示灯的个数

    * 第 2 行: 有n 个整数,如果第i 个整数O_i=0,表示第i 个盏灯初始的时候是关着的;如果O_i=1,表示第i 盏灯初始的时候是开着的。

    输出格式:

    1 行: 只有一个整数,表示最少需要多少步才能关上所有灯。

    输入输出样例

    输入样例#1: 复制
    4
    1 0 1 0
    输出样例#1: 复制
    6

    说明

    【输出解释】

    初始状态

    1010 第1 步

    1110 第2 步

    0110 第3 步

    0100 第4 步

    1100 第5 步

    1000 第6 步

    0000

    数据范围:

    对于40%的数据,n<=30

    对于70%的数据,n<=300

    对于100%的数据,n<=1000

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