八数码问题

题目描述
有N 只奶牛从左往右排成一行,编号是1 至N。这N 只奶牛当中,有一些奶牛是黑色的,其余的是白色的。color[i]表示第i 只奶牛的颜色,如果color[i]=0 则表示第i 头奶牛是黑色的,如果color[i]=1 则表示第i 头奶牛是白色的。六一奶牛儿童节快到了,农场主Farmer John 要从这N 头奶牛当中,挑选尽可能多的奶牛去参加晚会。Farmer John 挑选奶牛的原则是:挑选编号是连续的一段奶牛,这一段奶牛的颜色必须全部是白色的。Farmer John 有一个魔法棒,每用一次魔法棒就可以把一头黑色的奶牛变成一头白色的奶牛,魔法棒最多只能使用K 次。 在上述条件下,最多可以有多少头奶牛去参加晚会呢?
输入
第一行,两个整数,N 和K。
第二行,N 个整数,第i 个整数就是color[i],color[i]要么是0,要么是
1。
输出
一个整数,表示最多有多少头奶牛可以去参加晚会。
样例输入
Sample Input1:
11 0
1 1 0 0 1 1 1 1 0 1 1
Sample Input2:
11 1
1 1 0 0 1 1 1 1 0 1 1
样例输出
Sample Output1:
4
由于K=0,所以不能使用魔法棒,所以挑选编号是5 至8 的奶牛去参加
晚会。
Sample Output2:
7
由于K=1,所以最多可以使用1 次魔法棒,使用魔法棒把第9 头奶牛变成白色奶牛,然后挑选编号是5 至11 的奶牛去参加晚会。
数据范围限制
​ 对于50%的数据,1 <= N <= 1000,K = 0,即不能使用魔法棒。
对于100%的数据,1 <= N <= 100000, 1 <= K <=N。

信息

ID
1188
难度
10
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
6
已通过
0
通过率
0%
被复制
4
上传者