T-shirts

题目描述

AtCoder Inc. sells T-shirts with its logo. 你得到长度为 $N$ 的字符串 $S$，表示高桥在 $N$ 天的日程，字符串由 $0$、$1$ 和 $2$ 组成。
具体地，对满足 $1\leq i\leq N$ 的整数 $i$，

如果 $S$ 的第 $i$ 个字符是 $0$，第 $i$ 天他没有安排； 如果 $S$ 的第 $i$ 个字符是 $1$，第 $i$ 天他计划外出吃饭； 如果 $S$ 的第 $i$ 个字符是 $2$，第 $i$ 天他计划参加算法竞赛相关活动。

高桥有 $M$ 件普通 T 恤，且在第 1 天之前都已洗净并可穿着。
此外，为了满足下面的条件，他会购买若干带有 AtCoder 徽标的 T 恤。

在外出吃饭的日子，他会穿普通或徽标 T 恤。 在参加算法竞赛相关活动的日子，他会穿徽标 T 恤。 在没有安排的日子，他不会穿任何 T 恤，并且会把此时穿过的所有 T 恤洗干净。从次日开始可以再次穿这些 T 恤。 一旦穿过一件 T 恤，在洗之前不能再次穿它。

确定为了在这 $N$ 天内的所有安排日穿合适的 T 恤，他至少需要购买多少件 T 恤。如果他不需要购买新的 T 恤，输出 $0$.
假设购买的 T 恤也在第 1 天之前洗净并可穿着。

输入格式

The input is given from Standard Input in the following format: $N$ $M$ $S$

输出格式

打印高桥需要购买的最少徽标 T 恤数量，以便满足题目陈述中的条件。
如果他不需要购买新的 T 恤，输出 $0$。

6 1
112022

2

3 1
222

3

2 1
01

0

提示

$1\leq M\leq N\leq 1000$ $S$ is a string of length $N$ consisting of $0$, $1$, and $2$. $N$ and $M$ are integers.如果高桥购买两件徽标 T 恤，他可以如下穿着 T 恤：

第 1 天，他穿一件徽标 T 恤去吃饭。 第 2 天，他穿一件普通 T 恤去吃饭。 第 3 天，他穿一件徽标 T 恤参加算法竞赛相关活动。 第 4 天，他没有安排，所以他洗掉所有穿过的 T 恤。这样可以重复使用第 1、2、3 天穿过的 T 恤。 第 5 天，他穿一件徽标 T 恤参加算法竞赛相关活动。 第 6 天，他穿一件徽标 T 恤参加算法竞赛相关活动。

如果他购买一件或更少的徽标 T 恤，无论如何都无法用 T 恤满足条件。因此输出 $2$.
他不需要购买新 T 恤。

标签: AtCoder|abc332C

来源

AtCoder|abc332C