坏掉的项链（洛谷P1203题题解，C++语言描述）

题目要求

题目链接

分析

链子是循环的，随便选一点断开不合适，所以把它作为一个线性的字符串其实不好。

处理方法是将字符串扩增一倍，即necklace += necklace;

这样的话，我们从初始出发，必然能遍历整个链子且不受出发点的影响。

我的思路类似于非递归的斐波那契数列，设置一个prev一个temp，比较result和prev+temp的大小，取最大值。

遍历的时候细节有很多：

1. 先初始化prev，要小心w作为开头，因为w相当于邻近的r或b
2. 每一轮都考虑当前r或b，尽可能多地取，包含w也取下来，统计temp
3. r e s u l t = m a x ( r e s u l t , t e m p + p r e v ) result = max(result, temp+prev) result=max(result,temp+prev)
4. 更新prev，不能更新为temp，而还要考虑到本轮初始的i前面的w，所以要加上

于是乎，我WA了三个数据点，如下：

测试用例2输入：

3
rrr

测试用例2输出：

3

测试用例4输入：

17
wwwwwwwwwwwwwwwww

测试用例4输出：

17

测试用例6输入：

8
rrwwwwbb

测试用例6输出：

8

分别是三处细节问题，本质是一样的，即我没有考虑到一遍就跑完的情况，重复导致额外多加了很多。

处理方法是补充原则性判断 i < n i < n i> n >> necklace; // 复制一份 necklace += necklace; char prev_c, temp_c; // 合并最初的w while ((necklace[i] == 'w') && i