← 返回题目列表

Codeforces · 1216/F

F. 无线网络连接

中文机器翻译题面 查看原题

你在宿舍里担任系统管理员,宿舍里沿着笔直的走廊有一个又一个的房间。房间编号从 $$$1$$$ 到 $$$n$$$。

您必须将所有 $$$n$$$ 房间连接到互联网。

每个房间都可以直接连接互联网,第 $$$i$$$ 个房间的连接费用为 $$$i$$$ 金币。

部分房间还设有放置路由器的位置。在第 $$$i$$$ 个房间放置路由器的成本也是 $$$i$$$ 个硬币。您不能将路由器放置在没有放置位置的房间中。当您在房间$$$i$$$中放置路由器时,您将所有编号从$$$max(1,~i - k)$$$到$$$min(n,~i + k)$$$的房间连接到互联网,其中$$$k$$$是路由器的范围。 $$$k$$$ 的值对于所有路由器都是相同的。

计算将所有 $$$n$$$ 房间连接到互联网的最低总成本。您可以假设具有路由器位置的房间数量不大于您拥有的路由器数量。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$) — 房间数量和每个路由器的范围。

输入的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由零和一组成。如果字符串的第 $$$i$$$ 个字符等于“1”,则第 $$$i$$$ 个房间中有一个路由器位置。如果字符串的第 $$$i$$$ 个字符等于“0”,则不能将路由器放置在第 $$$i$$$ 个房间中。

输出

打印一个整数 — 将所有 $$$n$$$ 房间连接到互联网的最低总成本。

示例

输入 #1

5 2
00100

输出 #1

3

输入 #2

6 1
000000

输出 #2

21

输入 #3

4 1
0011

输出 #3

4

输入#4

12 6
000010000100

输出#4

15

注意

在第一个示例中,将路由器放置在房间 $$$3$$$ 中就足够了,然后所有房间都将连接到互联网。连接总成本为 $$$3$$$。

在第二个示例中,您可以将路由器放置在任何地方,因此您需要直接连接所有房间。因此,所有房间的总连接成本为 $$$1 + 2 + 3 + 4 + 5 + 6 = 21$$$。

在第三个示例中,您需要直接连接房间$$$1$$$,并将路由器放置在房间$$$3$$$中。因此,所有房间的总连接成本为 $$$1 + 3 = 4$$$。

在第四个示例中,您需要将路由器放置在 $$$5$$$ 和 $$$10$$$ 房间中。然后所有房间都将连接到互联网。连接总成本为 $$$5 + 10 = 15$$$。