外站题

徐老师的机器命令

文件读写

输入文件shell.in

输出文件shell.out

限制 1000ms 512MB

题目描述

100% 1 ≤ n ≤ 50000 1 ≤ ai ≤ n 3 [(1), 3,(2), 2, 1,(3), 2, 2, 1, 3, 2, 2, 1, 3, 2, 2]最近黄老师到徐老师家做客，但是没想到机器人的控制器居然被徐老师放在了沙发上 于是黄老师一屁股坐在了控制器上，在黄老师做完客离开家里以后 徐老师发现机器人被输入了一连串的指令！ 但是幸好的是，机器人收到的指令中只有两种指令：充电© 和 移动(M) 这让徐老师相当心疼，因为机器人进行移动是会导致磨损的！ 而徐老师当然可以擦除机器人现在收到的指令序列，但是擦除指令也会对机器人造成损伤！ 机器人现在的指令序列可以用一个仅包含 和 的字符串表示 由于随机擦除指令会极大的影响机器人的 使用寿命，所以徐老师只会从指令序列的开 头或者结尾擦除指令，不会擦除中间的指令 即如果指令序列为 ，徐老师可以擦除开头的指令变成 可以擦除结尾的指令变成 ，也可以两段都擦除一部分变成 ，当然也可以不擦除任何命令 这样可以让徐老师擦除指令时对机器人的损伤达到最小，但是不可避免的损伤依旧存在两种：

1. 擦除指令时，每擦除一个 指令会对机器人造成 点 损伤
2. 剩余的指令集中，每存在一个 指令会对机器人造成 点物理损伤 徐老师只会关心两种损伤中比较大的损伤是多少 现在徐老师想知道，对于一个指令序列，怎么擦除指令可以使得机器人最终受到的损伤最小？ 输入格式 第一行包含一个整数 表示有多组测试数据 对于每组测试数据包含一行仅由大写字母 组成的字符串，其中 代表充电指令， 代表移动指令 输出格式 对于每组测试数据，输出一行包含一个整数表示最小的损伤 C M CPU CCMMCC CMMCC, MMCC, MCC … CCMMC, CCMM, CCM, CC … CMMC, MM, M … C 1 CPU M 1 T C, M C M数据范围 数据点编号 字符串长度 其他 无 每个指令序列中不超过 个 每个指令序列中不超过 个 无 对于 的数据保证， 样例输入1 5 CMCCCMCCM CMMCMMCMMCMMC MMMMCCCCCC MMMMM CCCC 样例输出1 1 3 0 0 0 样例解释1 第一组测试数据： 移除的 有 个，剩余的 有 个，损伤为 第二组测试数据： 移除的 有 个，剩余的 有 个，损伤为 len 1 ∼ 3 1 ≤ len ≤ 100 4 ∼ 5 1 ≤ len ≤ 20000 10 C 6 ∼ 7 1 ≤ len ≤ 20000 10 M 8 ∼ 10 1 ≤ len ≤ 20000 100% 1 ≤ T ≤ 10 CMCCCMCCM → (CM)CCCMCC(M) C 1 M 1 max(1, 1) = 1 CMMCMMCMMCMMC → (CMMCMM)CMMC(MMC) C 3 M 2 max(3, 2) = 3第三组测试数据： 移除的 有 个，剩余的 有 个，损伤为 第四组测试数据： 移除的 有 个，剩余的 有 个，损伤为 第五组测试数据： 移除的 有 个，剩余的 有 个，损伤为 以上对于每组测试数据均只提供一种可能方案，方案可能不止一种 徐老师的地下堡 文件读写 输入文件game.in 输出文件game.out 限制 1000ms 512MB 题目描述 徐老师最近回归了一个著名老牌游戏——《魔兽世界》 在新版本中有一个单人副本模式《地下堡》，这可真是太利好徐老师这样的单人玩家了 于是徐老师在家里从早刷到晚，刷的昏天暗地，天旋地转 在梦里，徐老师依旧在刷地下堡，但是他梦到了一个神奇的地下堡副本，这个副本是一条直 线，一共有 个房间排成一排编号分别为 ，徐老师必须从 号房间进入，从 号 房间结束副本 MMMMCCCCCC− > (MMMM)CCCCCC C 0 M 0 max(0, 0) = 0 MMMMM− > (MMMMM) C 0 M 0 max(0, 0) = 0 CCCC− > CCCC C 0 M 0 max(0, 0) = 0

大佬给个代码啊