2092: 黑白棋游戏

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0

题目描述

贝贝将一些黑白棋子从左往右排成一行,给它们编号从 1 到 n ,棋子一部分是黑色的,另一部分是白色的。
用 color[ i ] 表示第 i 颗棋子的颜色,如果 color[ i ] = 0 表示第 i 粒棋子是黑色的,如果 color[ i ] = 1 表示第 i 粒棋子是白色的。

贝贝让他的哥哥浩然从这 n 粒棋子中按照下列的规则挑选出最长的序列:
① 挑选编号是连续的一段棋子,且必须是白色棋子;
② 浩然有 k 次机会让一粒黑色棋子变成白色棋子。

请你帮浩然算一下他可以挑选出的序列的最大长度是多少呢?

输入格式

第一行:两个整数 n k,分别表示共有 n 粒棋子,浩然有 k 次机会
第二行:n 个整数,表示 color [ i ],只能取 0 或者 1

输出格式

一个整数,表示浩然能挑选出的序列的最大长度

输入样例 复制

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

输出样例 复制

7

数据范围与提示

对于 50%的数据,1 <= n <= 1000,k = 0,即不能变
对于100%的数据,1 <= n <= 100000, 1 <= k <= n

样例中: k=1,所以最多可以变 1 次,把第 9 粒黑色棋子变成白色棋子,然后挑选出编号是 5 至 11 的棋子即得到了最长的序列。