P2438 [SDOI2005] Unlinking the Rings

Byteland has not always been a very democratic country, and it has some dark history. One fine day, General Byte (the commander of the country) decided to end the long civil war by releasing the imprisoned opposition. However, he did not set the opposition leader Baitesa (pinyin) completely free; instead, he locked Baitesa to the wall with a “Byte Chain”. The chain consists of many rings and a fence fixed to the wall. Although the rings are not fused with the fence, removing them is very difficult. “General, why are you chaining me to the wall instead of letting me go free!” Baitesa shouted. “Baitesa, you are not completely chained. I can frankly tell you that you can fully detach the rings from the fence,” General Byte replied, adding, “But you must work at night, finish within one hour, and make no noise. Otherwise, I will punish you according to the law.”

To help Baitesa! The rings on the chain are numbered $1, 2, \ldots, n$. We can detach them according to the following rules: - At each step, you may attach or detach exactly one ring to or from the fence. - Ring $1$ can always be attached or detached. - If rings $1, \ldots, k - 1$ are all detached and ring $k$ is attached, where $1 \le k < n$, then you may attach or detach ring $k + 1$. Write a program that, given the description of the Byte Chain, computes the minimum number of operations needed to remove all rings from the fence and outputs the result.

The first line contains an integer $n$, where $1 \le n \le 1000$. The second line contains $n$ integers $o_1, o_2, \ldots, o_n$ (each is $0$ or $1$) separated by single spaces. If $o_i = 1$, then the $i$-th ring is attached to the fence; if $o_i = 0$, then the $i$-th ring is not attached.

Output a single integer: the minimum number of operations required to detach all rings from the fence.

Translated by ChatGPT 5