CF1216F Wi-Fi

你是一名宿舍的系统管理员，宿舍沿着一条直走廊有 $n$ 个房间，房间编号从 $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$，仅由数字 $0$ 和 $1$ 组成。如果第 $i$ 个字符为 '1'，则第 $i$ 个房间有路由器插槽；如果为 '0'，则不能在第 $i$ 个房间放置路由器。

输出一个整数——将所有 $n$ 个房间连接到互联网的最小总费用。

在第一个样例中，只需在第 $3$ 个房间放置一个路由器，所有房间都能连接到互联网，总费用为 $3$。 在第二个样例中，所有房间都没有插槽，因此需要将每个房间都直接连接，总费用为 $1 + 2 + 3 + 4 + 5 + 6 = 21$。 在第三个样例中，需要将第 $1$ 个房间直接连接，并在第 $3$ 个房间放置一个路由器，总费用为 $1 + 3 = 4$。 在第四个样例中，需要在第 $5$ 和第 $10$ 个房间放置路由器，所有房间都能连接到互联网，总费用为 $5 + 10 = 15$。 由 ChatGPT 4.1 翻译