#P1805. 关灯

    ID: 831 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>NOI 导刊递推线性递推递推式高精度

关灯

题目描述

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

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

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

  • 每一步只能开或关一盏灯。
  • 编号为 11 的灯可以随意开或关。
  • 如果编号为 1,2,,k11, 2, \cdots,k-1 的灯都关上了了,并且编号为 kk 的灯在开着,我们可以随意开或关第 k+1k+1 盏灯。

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

输入格式

11 行一个整数 nn,表示灯的个数。

22 行有 nn 个整数,如果第 ii 个整数 Oi=0O_i=0,表示第 ii 个盏灯初始的时候是关着的;如果 Oi=1O_i=1,表示第 ii 盏灯初始的时候是开着的。

输出格式

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

4
1 0 1 0
6

提示

【输出解释】

  • 初始状态 10101010
  • 1111101110
  • 2201100110
  • 3301000100
  • 4411001100
  • 5510001000
  • 6600000000

数据范围及约定

  • 对于 40%40\% 的数据,n30n \le 30
  • 对于 70%70\% 的数据,n300n \le 300
  • 对于 100%100\% 的数据,n1000n \le 1000