为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/beads
目录 |
[编辑] 思路一
这道题用标准的搜索是O(n^2)的，可以用类似动态规划的方法优化到O(n)。
用数组bl,br,rl,rr分别记录在项链i处向左向右收集的篮色红色珠子数。
项链是环形的，但我们只要把两个同样的项链放在一块，就把它转换成线性的了。
我们只要求出bl,br,rl,rr，那么结果就是max(max(bl[i],rl[i])+max(br[i+1],rr[i+1])) (0<=i<=2*n-1)。
我们以求bl,rl为例:
初始时bl[0]=rl[0]=0
我们从左往右计算
如果necklace[i]='r',rl[i]=rl[i-1]+1,bl[i]=0；
如果necklace[i]='b', bl[i]=bl[i-1]+1,rl[i]=0；
如果necklace[i]='w',bl[i]=bl[i-1]+1,rl[i]=rl[i-1]+1。
同理可以求出br,rr。
(DP+mod):按这个动规的思路，还有另外一种变形，用模运算来处理环
这样初值不能简单地用bl[0]=rl[0]=0来表示，我们没有任何理由认为0位置应当为初始位置（在用模运算处理环的情况下）
应该在项链中找到第一个'b'，则此位置的rl,rr都为0,从这个位置按照上面的递归关系进行DP计算rl,rr，如果没有'b',那么整个项链都可看做红色，直接输出n即可。同理，可以计算bl,br以及最后的结果，简洁的C代码已贴在代码页。
事实上不必使用动态规划，直接搜索亦可达到O(n)。
把两个同样的项链放在一块，从头开始用两个变量(变量)a,b记录自左方某点至目前为止可搜集到之两种颜色珠子数，
取途中所出现a+b之最大值，遇颜色变换时再将b指定给a即可，代码十分简洁。
[编辑] 思路二
每次将串s的首位移动至末位，每次均能从两头开始搜索，无需考虑环的问题。
[编辑] 思路三
无需考虑w的。进行分类讨论，只有rb和br两种情况。 但是如果是rrrrwbbbbrb呢？?
问：如何解决w的重复运算与漏算问题？ w的漏算很容易考虑，至于重算的情况那得到的总长度必然超过n，这种情况下显然是可以把所有珠子都取出来的。直接输出n就可以了。
PASCAL注意 此题必须ANSISTRING（超长字符串） (用数组操作也很方便）
[编辑] 思路四
首先记下所有的颜色变化点 在每个颜色变化点上进行如下操作： 若该点为b或r，向右查找，找到结尾之后返回开头继续查找，每发现一颗珠子就将长度加一，允许变色一次，变色机会用完后终止，与上一个变色点的长度比较，保留长的。 若该点为w，向右查找，找到结尾之后返回开头继续查找，每发现一颗珠子就将长度加一，允许变色两次，两次变色机会用完后终止，与上一个变色点的长度比较，保留长的。
