A16538 | $Sleeping Through Classes$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

你今天有 $n$ 节课，编号从 $1$ 到 $n$。 这些课程由一个长度为 $n$ 的二进制字符串 $s$ 描述。我们称第 $i$ 节课为重要课当且仅当 $s_i = 1$。对于每一节重要课，你必须保持清醒并听课。 你非常疲倦，想尽可能多地在课上睡觉。然而，入睡需要时间。如果你听了一节重要课 $i$，那么接下来的 $k$ 节课你都无法入睡，也就是说你必须在第 $i+1, i+2, \ldots, i+k$ 节课中保持清醒（如果后面的课程少于 $k$ 节，则直到今天上完为止）。 对于不重要的课程，你可以选择睡觉，除非前面的规则要求你保持清醒。 你的任务是计算今天最多能睡多少节课。 $^\text{∗}$二进制字符串是指字符串中的每个字符都是 $0$ 或 $1$。

每个测试用例包含多组数据。第一行为测试用例数 $t$（$1 \le t \le 500$）。 每组测试数据的第一行为两个整数 $n$ 和 $k$（$1 \le n, k \le 100$）。 每组测试数据的第二行为一个长度为 $n$ 的字符串 $s$（$s_i = 0$ 或 $s_i = 1$）。

对于每组测试数据，输出一个整数，表示你今天最多能睡多少节课。

输入 #1

输出 #1

C++ 编辑器

输入

输出