4107: 需要准备几件T恤衫?

内存限制：1024 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

# T-shirts ## 题目描述 小高有一个为期 N 天的日程安排，用一个长度为 N 的字符串 S 表示。其中: - 如果第 i 天的字符是 '0'，表示那天没有安排； - 如果是 '1'，表示那天计划外出就餐； - 如果是 '2'，表示那天计划参加编程比赛。 小高有 M 件普通T恤，在第一天之前都是洗好可以穿的。为了满足以下条件，他还需要购买一些带AtCoder标志的T恤: - 外出就餐时，他会穿普通T恤或带标志的T恤。 - 参加编程比赛时，他必须穿带标志的T恤。 - 没有安排的日子，他不会穿T恤。同时他会洗所有到那时为止穿过的T恤，从第二天开始可以再次穿这些T恤。 - 一件T恤穿过后，在洗之前不能再穿。 请计算小高最少需要购买多少件带标志的T恤，才能在这 N 天内满足所有条件。如果不需要购买新T恤，输出 0。

输入

## 输入格式 输入从标准输入中给出，格式如下: ``` N M S ```

输出

## 输出格式 输出小高需要购买的最少T恤数量。如果不需要购买新T恤，输出0。

样例输入 复制 

6 1
112022

样例输出 复制 

2

提示

## 输入输出样例 ### 输入样例1 ``` 6 1 112022 ``` ### 输出样例1 ``` 2 ``` ### 输入样例2 ``` 3 1 222 ``` ### 输出样例2 ``` 3 ``` ### 输入样例3 ``` 2 1 01 ``` ### 输出样例3 ``` 0 ``` ## 数据范围与提示 【样例说明1】 如果小高购买两件带标志的T恤，他可以按以下方式穿T恤: - 第一天，他穿一件带标志的T恤外出就餐。 - 第二天，他穿一件普通T恤外出就餐。 - 第三天，他穿一件带标志的T恤参加编程比赛。 - 第四天，他没有安排，所以他洗了所有穿过的T恤。这样他就可以重新使用第一、二、三天穿过的T恤。 - 第五天，他穿一件带标志的T恤参加编程比赛。 - 第六天，他穿一件带标志的T恤参加编程比赛。 如果他购买一件或更少的带标志T恤，无论如何都无法满足条件。因此，输出 2。 【样例说明3】 他不需要购买新的T恤。 【数据范围】 $1 ≤ M ≤ N ≤ 1000$，S 是一个长度为 N 的字符串，只包含 '0'、'1' 和 '2'，N 和 M 都是整数。 ## 题目来源 ABC332C
提交提交记录统计露一手!