AT_abc332_c [ABC332C] T-shirts

题目描述

AtCoder 社正在销售带有 Logo 的 T 恤。

高桥君的 $N$ 天的日程安排由一个仅包含 0、1、2 的长度为 $N$ 的字符串 $S$ 给出。
具体来说，对于满足 $1 \leq i \leq N$ 的整数 $i$：

• 当 $S$ 的第 $i$ 个字符为 0 时，第 $i$ 天没有任何安排。
• 当 $S$ 的第 $i$ 个字符为 1 时，第 $i$ 天高桥君有外出吃饭的计划。
• 当 $S$ 的第 $i$ 个字符为 2 时，第 $i$ 天高桥君有参加竞赛编程活动的计划。

高桥君拥有 $M$ 件无印 T 恤，并且在第 $1$ 天开始前，这些 T 恤都已经洗净。
此外，为了能够满足以下条件，高桥君可以购买若干件带有 AtCoder Logo 的 T 恤：

• 外出吃饭的日子，需要穿一件无印 T 恤或一件带 Logo 的 T 恤。
• 参加竞赛编程活动的日子，必须穿一件带 Logo 的 T 恤。
• 没有安排的日子不需要穿 T 恤，并且此时会把已经穿过的所有 T 恤都洗净。洗净后的 T 恤从第二天起可以再次穿。
• 一件 T 恤在下次洗净之前不能再次穿。

请计算，为了保证在 $N$ 天内所有有安排的日子都能满足上述条件，高桥君最少需要购买多少件带 Logo 的 T 恤。如果不需要购买新的 T 恤，则输出 $0$。
注意，新购买的 T 恤在第 $1$ 天开始前也都已经洗净。

输入格式

输入以如下格式从标准输入读入：

$N$ $M$ $S$

输出格式

请输出为了满足题目条件，高桥君最少需要购买的带 Logo 的 T 恤数量。如果不需要购买新的 T 恤，则输出 $0$。

输入输出样例 #1

输入 #1

6 1
112022

输出 #1

2

输入输出样例 #2

输入 #2

3 1
222

输出 #2

3

输入输出样例 #3

输入 #3

2 1
01

输出 #3

0

说明/提示

限制条件

• $1 \leq M \leq N \leq 1000$
• $S$ 是一个仅包含 0、1、2 的长度为 $N$ 的字符串
• $N, M$ 均为整数

样例解释 1

当高桥君购买了 $2$ 件带 Logo 的 T 恤时，可以如下安排穿着：

• 第 $1$ 天，高桥君穿带 Logo 的 T 恤去吃饭。
• 第 $2$ 天，高桥君穿无印 T 恤去吃饭。
• 第 $3$ 天，高桥君穿带 Logo 的 T 恤去参加竞赛编程活动。
• 第 $4$ 天没有安排，因此将第 $1,2,3$ 天穿过的 T 恤全部洗净，可以再次穿。
• 第 $5$ 天，高桥君穿带 Logo 的 T 恤去参加竞赛编程活动。
• 第 $6$ 天，高桥君穿带 Logo 的 T 恤去参加竞赛编程活动。

如果高桥君只购买 $1$ 件或更少的带 Logo 的 T 恤，则无法满足所有条件。
因此，输出 $2$。

样例解释 3

高桥君不需要购买新的 T 恤。

由 ChatGPT 4.1 翻译