logo AlgoBeat OnlineJudge
登录 注册

#10077. [Sleeping Cup #7] B. Rice Cake Consumption

内存限制:512 MiB 时间限制:1000 ms 输入文件:ricecake.in 输出文件:ricecake.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

注记:

由于质量原因,本场的 A 题没有搬入;由于评测原因,上场整场没有搬入。

四个子任务对应的测试点编号分别为:1 - 10,11 - 18,19 - 20,21 - 25;其中测试点 11 / 19 为样例 1,测试点 12 为样例 2。

这天晚上,Sleeping Goose 买了一串涂了辣椒酱的年糕。

Sleeping Goose 所买到的年糕的竹签上有 个位置可以串年糕,但有的位置串了年糕(年糕不能移动),有的位置则没有。

Sleeping Goose 希望按照某种顺序吃掉每一块年糕,但它希望尽量不蹭掉辣椒酱。具体来说,当它选择吃掉某一块年糕时,它的嘴会蹭到其他所有距离它不超过 个位置的年糕。

Sleeping Goose 的嘴每蹭到某一块年糕一次,就会有 单位辣椒酱被蹭下来。现在它想问你:在最优的吃法下,它一共会蹭掉多少单位辣椒酱?

输入格式

本题有多组数据。

第一行输入一个整数 ,表示测试数据的数量。

对于每组测试数据:

第一行两个整数

第二行一个长度为 的 01 串 ,描述 Sleeping Goose 所买到的年糕,其中 1 代表对应位置有年糕,0 代表对应位置没有年糕。

输出格式

对于每组数据,输出一行一个整数,表示 Sleeping Goose 在最优的吃法下一共会蹭掉多少单位辣椒酱。

样例

样例输入 #1

2
1 0
1
7 6
0000000

样例输出 #1

0
0

样例输入 #2

2
9 1
111010111
32 12
00110000100000000001000000110110

样例输出 #2

4
14

数据范围与提示

样例 2 解释

对于第一组数据,一种最优的吃法如下:

  • 吃掉位置 的年糕。
  • 吃掉位置 的年糕,蹭到位置 的年糕。
  • 吃掉位置 的年糕,蹭到位置 的年糕。
  • 吃掉位置 的年糕。
  • 吃掉位置 的年糕,蹭到位置 和位置 的两块年糕。
  • 吃掉位置 的年糕。
  • 吃掉位置 的年糕。

数据范围

对于 的数据,

本题共有四个等分的子任务,各子任务的特殊限制如下:

  1. 保证
  2. 无特殊限制。