#P1805. 关灯
关灯
题目描述
在某条道路上,有 盏灯排成一排,它们有的是开着的,有的是关着的。
由于天马上就要亮了,上级给了你一个任务:把所有的灯都关掉。
只不过,这些灯都比较智能,不会被轻易关掉。它们的开或关遵循如下规则:
- 每一步只能开或关一盏灯。
- 编号为 的灯可以随意开或关。
- 如果编号为 的灯都关上了了,并且编号为 的灯在开着,我们可以随意开或关第 盏灯。
在关灯之前,请你计算:至少要多少步才能关上所有灯?
输入格式
第 行一个整数 ,表示灯的个数。
第 行有 个整数,如果第 个整数 ,表示第 个盏灯初始的时候是关着的;如果 ,表示第 盏灯初始的时候是开着的。
输出格式
共一行一个整数,表示最少需要多少步才能关上所有灯。
4
1 0 1 0
6
提示
【输出解释】
- 初始状态 ;
- 第 步 ;
- 第 步 ;
- 第 步 ;
- 第 步 ;
- 第 步 ;
- 第 步 。
数据范围及约定
- 对于 的数据,;
- 对于 的数据,;
- 对于 的数据,。