#YDRG002A. 琉金云间
琉金云间
题目描述
Yoimiya 有 堆火药,有一个长度为 的 01 字符串描述这些火药,第 堆火药能点燃当且仅当 .
假设当前还剩 堆火药,编号从小到大依次为 ,可以选择一堆能点燃的火药 ,将其点燃,其会引爆第 堆火药并让其消失,但第 堆火药不会消失并且在此后依然能被点燃。
注意,虽然火药的编号变了,但是可燃性不会改变。
Yoimiya 想要烟火尽可能地为世人绽放,请求出至多能点燃几次火药。
输入格式
第一行,一个整数 .
第二行,一个长度为 的 01 字符串 .
输出格式
一个整数,代表答案。
样例 输入
5
00100
样例 输出
1
样例 输入
5
01010
样例 输出
3
样例解释
样例一:只能点燃 。
样例二:其中一种最优操作为:
点燃 ,使得 消失,字符串变为 0010
。
之后点燃一次 ,字符串变为 010
。
点燃一次 ,字符串变为 00
。
一共点燃 次。
测试点约束
对于 的数据,.
各测试点的约束如下表所示,其中 表示字符串中有多少字符 1
:
测试点编号 | ||
---|---|---|
Related
In following contests: