#P3240. 黑白奶牛 (cow)

黑白奶牛 (cow)

题目描述

有 N 只奶牛从左往右排成一行,编号是 1 到 N。这些奶牛里,有的是黑色,剩下的是白色,用数组 color[i] 表示第 i 只奶牛的颜色:如果 color[i] 是 0,说明这头奶牛是黑色;如果 color[i] 是 1,说明这头奶牛是白色。

六一奶牛儿童节快到了,农场主 Farmer John 要从这些奶牛里挑尽可能多的奶牛去参加晚会,挑选要遵守以下规则:

  1. 挑选的奶牛编号必须是连续的一段;
  2. 这一段奶牛的颜色必须全部是白色,黑色奶牛可以用魔法棒变成白色来满足这个条件。

Farmer John 有一根魔法棒,每用一次就能把一头黑色奶牛变成白色,但魔法棒最多只能用 K 次。请你计算在这样的限制下,最多能有多少头奶牛去参加晚会。

输入格式

  1. 第一行:两个整数 N 和 K,分别表示奶牛的总数和魔法棒最多能使用的次数。
  2. 第二行:N 个整数,依次是 color[1]、color[2]、……、color[N],每个数都是 0 或 1,代表对应编号奶牛的颜色。

输出格式

输出一个整数,表示最多可以参加晚会的奶牛数量。

样例输入 1

11 0
1 1 0 0 1 1 1 1 0 1 1

样例输出 1

4

样例解释 1

因为 K=0,没办法使用魔法棒,所以要选完全由白色奶牛组成的最长连续段。编号 5 到 8 的奶牛都是白色,它们的颜色依次是 1、1、1、1,一共 4 头,这是最长的符合条件的段。

样例输入 2

11 1
1 1 0 0 1 1 1 1 0 1 1

样例输出 2

7

样例解释 2

因为 K=1,最多能使用 1 次魔法棒。把编号 9 的黑色奶牛(color[9]是 0)变成白色后,编号 5 到 11 的奶牛形成连续的白色段,一共 11-5+1=7 头,这是最大数量。

数据范围

数据规模 约束条件
50% 1 ≤ N ≤ 1000,K=0,不能使用魔法棒
100% 1 ≤ N ≤ 100000,1 ≤ K ≤ N