← 返回题目列表

Codeforces · 1066/B

B. 加热器

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

Vova 的房子是一个由 $$$n$$$ 元素组成的数组(是的,我认为这是第一个问题,有人住在数组中)。阵列的某些位置有加热器。如果 $$$i$$$ 位置有加热器,则数组的第 $$$i$$$ 元素为 $$$1$$$,否则数组的第 $$$i$$$ 元素为 $$$0$$$。

每个加热器都有一个值 $$$r$$$ ($$$r$$$ 对于所有加热器都是相同的)。该值意味着 $$$pos$$$ 位置处的加热器可以加热 $$$[pos - r + 1; 范围内的所有元件; pos + r - 1]$$$。

Vova 喜欢一边思考一边在他的房子里走来走去,他讨厌房子的寒冷位置。 Vova 希望打开他的一些加热器,这样他房子的每个部分都将由至少一个加热器加热。

Vova 的目标是加热整个房子(数组的所有元素),即如果 $$$n = 6$$$、$$$r = 2$$$ 且加热器位于 $$$2$$$ 和 $$$5$$$ 位置,那么如果 Vova 打开房子中的所有加热器,则可以加热整个房子(然后前 $$$3$$$ 元素将被加热)由第一个加热器加热,最后 $$$3$$$ 元件将由第二个加热器加热)。

最初,所有加热器都关闭。

但从另一方面来说,Vova 并不喜欢为电费支付太多费用。因此,他希望打开最少数量的加热器,以便他的房子的每个元件都至少由一个加热器加热。

你的任务是找到这个数量的加热器或者说不可能让整个房子变暖​​。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$r$$$ ($$$1 \le n, r \le 1000$$$) — 数组中的元素数量和加热器的值。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$) — Vova 的房屋描述。

输出

打印一个整数——加热整个房子所需的最少加热器数量,如果不可能的话,打印 -1。

示例

输入 #1

6 2
0 1 1 0 0 1

输出 #1

3

输入 #2

5 3
1 0 0 0 1

输出 #2

2

输入 #3

5 10
0 0 0 0 0

输出 #3

-1

输入#4

10 3
0 0 1 1 0 1 0 0 0 1

输出#4

3

注意

在第一个示例中,位于 $$$2$$$ 位置的加热器加热元件 $$$[1; 3]$$$,位置$$$3$$$的加热器加热元件$$$[2, 4]$$$,位置$$$6$$$的加热器加热元件$$$[5; 6]$$$ 所以答案是$$$3$$$。

在第二个示例中,位于 $$$1$$$ 位置的加热器加热元件 $$$[1; 3]$$$并且位于$$$5$$$位置的加热器加热元件$$$[3; 5]$$$ 所以答案是$$$2$$$。

在第三个示例中,没有加热器,因此答案为 -1。

在第四个示例中,位于 $$$3$$$ 位置的加热器加热元件 $$$[1; 5]$$$,$$$6$$$位置的加热器加热元件$$$[4; 8]$$$,$$$10$$$位置的加热器加热元件$$$[8; 10]$$$ 所以答案是$$$3$$$。