/ / 题库 /

(ty 1-5) 盖板子

(ty 1-5) 盖板子

测试数据来自 nnu_contest/5c1246cbe561762f52b33c76

Cow Bessie想要去探险,它来到一座山前面,面前出现了n个洞口,这些洞口排在一条直线上。
这些洞口中有一些有陷阱,如果Bessie走进这些洞口就会受伤。
为了不让Bessie受伤,你找来了一些板子,要将那些有陷阱的洞口盖住。你找到了k个板子,这些板子可以是任意长度,也就是说,板子可以拉伸。
为了让Bessie去更多安全的洞口探险,你需要尽量少的使安全的洞口不被盖住。
现在问在盖住所有陷阱的情况下,你最少会盖住多少安全的洞口。
输入
第一行 三个整数k、p、n。k个板子、p个陷阱(3<=p<5000)、总洞口数n(1<n<10000)。
第二行 一个字符串,由01组成,表示所有洞口,0表示洞口安全,1表示洞口有陷阱
输出
一个整数,表示在盖住所有陷阱的情况下,最少会盖住多少安全的洞口。

样例输入

2 3 8
01001010

样例输出

1

解释
洞口 0 1 0 0 1 0 1 0
下标 0 1 2 3 4 5 6 7
设洞口下标从0开始,用两个板子,第一个长度为1,盖住下标为1的洞口;
第二个长度为3,盖住下标为4,5,6的洞口。
被盖住的4个洞口中只有洞口5安全,所以在盖住所有陷阱的情况下,最少盖住1个安全洞口。故输出1.

信息

ID
1272
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者