P13202 [GCJ 2016 #3] Teaching Assistant

你正在上一门以题集为评分方式的编程课程。课程持续天数为正偶数天。你开始时没有任何题集。在课程的每一天，你必须执行以下三种操作之一： * 申请一个“编程（Coding）”题集； * 申请一个“Jamming”题集； * 提交一个题集进行评分。你必须至少拥有一个题集才能选择此操作。如果你有多个题集，必须提交**最近申请的那一个**，无论其类型如何。 所有题集都是不同的。对提交题集的类型和数量没有要求。一旦你提交了某个题集，你就不再拥有该题集。任何在课程结束前未提交的题集都不会获得分数。 题集的申请和提交都通过一个人工智能助教完成。奇怪的是，助教每天都有不同的心情——每一天只会喜欢“Coding”或“Jamming”中的一种。 * 当你申请题集时： * 如果申请的题集类型与助教当天的心情一致，则该题集最高可得 10 分。 * 如果申请的题集类型与助教当天的心情不一致，则该题集最高可得 5 分。 * 当你提交题集时： * 如果提交的题集类型与助教当天的心情一致，则你能获得该题集的最高分。 * 如果提交的题集类型与助教当天的心情不一致，则你获得的分数比最高分少 5 分。 例如： * 如果你在助教心情为“Coding”的那天申请了一个“Coding”题集，并在助教心情为“Jamming”的那天提交，则你能获得 5 分：该题集最高分为 10 分，但助教会少给 5 分。 * 如果你在助教心情为“Coding”的那天申请了一个“Jamming”题集，并在助教心情为“Jamming”的那天提交，则你能获得 5 分：该题集最高分为 5 分，助教会给你最高分。 幸运的是，你有一位非常了解助教的师兄，他告诉了你课程每一天助教的心情。请问你最多能获得多少分？

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组一行，包含一个由 $\mathbf{C}$ 和/或 $\mathbf{J}$ 组成的字符串 $\mathbf{S}$。第 $i$ 个字符表示课程第 $i$ 天助教的心情，$\mathbf{C}$ 表示“Coding”，$\mathbf{J}$ 表示“Jamming”。

对于每组测试用例，输出一行 `Case #x: y`，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始），$\mathrm{y}$ 表示你在该组测试用例下能获得的最高分。

**样例解释** 对于样例第 1 组，最优策略如下： - 第 1 天：申请“Coding”题集（记为 C1）。 - 第 2 天：提交 C1。 - 第 3 天：申请“Jamming”题集（记为 J1）。 - 第 4 天：提交 J1。 对于样例第 2、3、4 组，最优策略为：先申请 C1，再申请 J1，然后提交 J1，最后提交 C1。 以第 2 组为例，注意你不能先申请 C1，再申请 J1，然后提交 C1。因为每次只能提交最近申请的题集。 对于第 5 组，你可以每隔一天申请一个“Coding”题集，下一天就提交它。 **限制条件** - $1 \leqslant \mathbf{T} \leqslant 100$。 - $\mathbf{S}$ 的长度为偶数。 **小数据集（5 分，测试集 1 - 可见）** - $2 \leqslant \mathbf{S}$ 的长度 $\leqslant 50$。 **大数据集（10 分，测试集 2 - 隐藏）** - $2 \leqslant \mathbf{S}$ 的长度 $\leqslant 20000$。 - 所有测试用例的 $\mathbf{S}$ 总长度不超过 150000。 翻译由 GPT4.1 完成。