P16861 [GKS 2021 #G] Dogs and Cats

你在一个动物收容所工作，负责喂养动物。你已经准备了 $D$ 份狗粮和 $C$ 份猫粮。 总共有 $N$ 只动物在排队，其中一些是狗，另一些是猫。也可能所有动物都是狗或都是猫。一个长度为 $N$ 的字符串 $S$，由字符 `C` 和 `D` 组成，表示队伍中猫和狗的顺序。如果队伍中的第 $i$ 只动物是猫，则第 $i$ 个字符为 `C`；如果是狗，则为 `D`。 动物按照它们在队伍中的顺序进食。每只狗恰好吃掉 $1$ 份狗粮，同样每只猫恰好吃掉 $1$ 份猫粮。此外，你还有额外的猫粮。每当一只狗吃完食物后，你会为猫带来 $M$ 份额外的猫粮。 动物必须按照它们在队伍中的顺序进食，并且只有当它前面的动物已经吃完后，它才能进食。这意味着，如果你用完了狗粮（或猫粮），而将要喂食的是一只狗（或猫），那么队伍将不会前进，所有动物都会耐心等待。 你需要判断在这种情况下，队伍中所有的狗是否都能被喂饱。注意，这意味着某些猫可能会留在队伍中，但不用担心，你稍后会喂它们！

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含四个整数 $N$、$D$、$C$ 和 $M$：分别表示动物的数量、初始的狗粮份数、初始的猫粮份数，以及在一只狗吃掉一份狗粮后额外添加的猫粮份数。 下一行包含一个长度为 $N$ 的字符串 $S$，表示动物的排列。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 `YES`（如果所有狗都能被喂饱）或 `NO`（否则）。

在样例 #1 中，有 $10$ 份狗粮和 $4$ 份猫粮。 - 前 $2$ 只动物是猫，它们吃完后，剩下 $2$ 份猫粮。 - 然后一只狗吃掉 $1$ 份狗粮，此时剩下 $9$ 份狗粮。 - 接下来一只猫吃掉 $1$ 份猫粮，猫粮剩余 $1$ 份。 - 最后 $2$ 只动物是狗，它们各吃掉 $1$ 份狗粮。 因此，在这个例子中，所有狗都能吃到食物。 在样例 #2 中，没有狗。因此，所有（$0$ 只）狗当然都能被喂饱。 在样例 #3 中，第二只狗前面的猫无法吃到食物，因为猫粮不够。因此，第二只狗也无法吃到食物。 ### 限制条件 $1 \le T \le 100$。 $1 \le N \le 10^4$。 $0 \le D, C \le 10^6$。 $S$ 仅由字符 `C` 和 `D` 组成。 **测试集 1** $M = 0$。 **测试集 2** $0 \le M \le 10^6$。 翻译由 DeepSeek V4 Pro 完成