题面描述:
在一款游戏中,玩家需要依次释放三种元素技能:火(F)、水(W)、土(E)。每个技能的基础能量值分别为:F 获得 1 点,W 获得 2 点,E 获得 3 点。技能释放时若与之前连续释放的相同技能产生共鸣,还会获得额外的共鸣奖励。具体而言,对于序列中的第 i 个技能,如果它与紧邻的前一个技能相同,则奖励 1 点;如果与前两个技能都相同,则再奖励 1 点,依此类推。换言之,设第 i 个技能之前有 k 个连续相同的技能,则它额外获得 k 点奖励。总能量为所有技能的基础能量与共鸣奖励之和。请计算给定技能序列的总能量。
思路:模拟遍历
由于string的长度只有1e4,可以直接暴力做,n^2也只有1e8,小常数1s内可以跑完。直接往前遍历有几个字符和它相同即可。
或者基于简单dp的方式,每个位置保存它前面与它相等且串联的字符数量,每个字符只需要看其是否与上一个字符相等即可,相等则加1,否则置为0。