drink

Luogu
IDLGP9517
Time1000ms
Memory512MB
DifficultyP1
贪心洛谷原创O2优化
你面前有 $n$ 个瓶子,从左到右依次编号为 $1 \sim n$,瓶子可能是空的也可能装着水。 你可以选择一对 $l,r(l \le r)$,然后把 $l\sim r$ 号瓶子中的所有水全部喝完。你想一口气把桌上剩的水全喝完,请问你最少要拿起几个瓶子? 你有可能一个瓶子都不需要拿起来。 ## Input 第一行一个整数 $n$。 第二行 $n$ 个整数,第 $i$ 个整数为 $1$ 表示第 $i$ 个瓶子装着水,为 $0$ 表示第 $i$ 个瓶子是空的。 ## Output 一行一个整数 $k$,表示最少拿起的瓶子数。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/8u8szw7z.png) ## Note **【样例说明】** 样例 $1$ 中,拿起 $4$ 号瓶子即可。总共拿起 $1$ 个瓶子。 样例 $2$ 中,拿起 $3\sim 6$ 号瓶子可以将所有的水喝完。总共拿起 $4$ 个瓶子。 **【数据范围】** 对于 $30\%$ 的数据,保证 $n\le 100$。 对于 $60\%$ 的数据,保证 $n\le 2000$。 对于 $100\%$ 的数据,保证 $1\le n\le 10^5$,$0\le a_i\le 1$。
Samples
Input #1
5
0 0 0 1 0
Output #1
1
Input #2
6
0 0 1 1 0 1
Output #2
4
API Response (JSON)
{
  "problem": {
    "name": "drink",
    "description": {
      "content": "你面前有 $n$ 个瓶子,从左到右依次编号为 $1 \\sim n$,瓶子可能是空的也可能装着水。 你可以选择一对 $l,r(l \\le r)$,然后把 $l\\sim r$ 号瓶子中的所有水全部喝完。你想一口气把桌上剩的水全喝完,请问你最少要拿起几个瓶子? 你有可能一个瓶子都不需要拿起来。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9517"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你面前有 $n$ 个瓶子,从左到右依次编号为 $1 \\sim n$,瓶子可能是空的也可能装着水。\n\n你可以选择一对 $l,r(l \\le r)$,然后把 $l\\sim r$ 号瓶子中的所有水全部喝完。你想一口气把桌上剩的水全喝完,请问你最少要拿起几个瓶子?\n\n你有可能一个瓶子都不需要拿起来。\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行 $n$ 个整数,第 $i$ 个整数为 $1$ 表...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments