P1805 Turning Off the Lights

Along a road, there are $n$ lights in a row; some are on, and some are off. Dawn is about to break, and you are given a task: turn all the lights off. However, these lights are rather smart and cannot be turned off easily. Their on/off behavior follows the rules below: - In each step, you may turn on or off exactly one light. - The light with index $1$ can be turned on or off freely. - If lights $1, 2, \cdots, k-1$ are all off and light $k$ is on, then you may freely turn on or off light $k+1$. Before turning off the lights, please compute the minimum number of steps needed to turn all the lights off.

The first line contains an integer $n$, the number of lights. The second line contains $n$ integers. If the $i$-th integer $O_i = 0$, the $i$-th light is initially off; if $O_i = 1$, the $i$-th light is initially on.

Output a single integer on one line, the minimum number of steps required to turn off all the lights.

[Output Explanation] - Initial state: 1010. - Step 1: 1110. - Step 2: 0110. - Step 3: 0100. - Step 4: 1100. - Step 5: 1000. - Step 6: 0000. Constraints - For $40\%$ of the testdata, $n \le 30$. - For $70\%$ of the testdata, $n \le 300$. - For $100\%$ of the testdata, $n \le 1000$. Translated by ChatGPT 5