原题：
You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:
1 2 1 2r b b r b r r br b b br r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead
The beads considered first and second in the text that follows have been marked in the picture.
The configuration in Figure A may be represented as a string of b’s and r’s, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .
Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).
Determine the point where the necklace should be broken so that the most number of beads can be collected.
题意：
有一串链子，由三种颜色的珠子组成：红r 、蓝b 、白w（可以当做红色也可以当做蓝色），从某一处断开，使得从断开处顺时针和逆时针分别取珠子，若碰到第一个不同色的珠子就停止，求最多取多少个珠子。
输入要求：
n（n<=400）字符串长度
str （只包含小写的[wbr]）字符串
题解：
暴力枚举通过这个题目是没有问题的，参见我的另一篇博文。
dp方法可以节约很多的运行时间。我们首先将字符串复制并追加在原字符串尾部，这样就可以将环变成线性的。
我们使用四个数组：leftB[i] leftR[i] rightB[i] rightR[i]来表示在第i个字符左边出现的最多连续的b、r的数量（不包括其本身），以及i右边出现的最多连续的b，r的数量（包括其本身,这样可以等价于在i珠子和i-1珠子中间断开），数组的初始值都为0.
由于字符串是原来的字符串两个相连的，如果向左和向右碰头了就会导致重复计算珠子，但是碰头就代表全部可以取，所以将碰头的结果全部置为n，所以并不影响我们使用dp。
状态转移方程：
先计算左边的
第i个字符为r：rightR[i]=rightR[i+1]+1;
为b：rightB[i]=rightB[i+1]+1;
为w：rightR[i]=rightR[i+1]+1;
rightB[i]=rightB[i+1]+1;
再计算右边的
第i个字符为r： rightR[i]=rightR[i+1]+1;
为b： rightB[i]=rightB[i+1]+1;
为w： rightR[i]=rightR[i+1]+1;
rightB[i]=rightB[i+1]+1;
最终遍历四个数组，ans=max（max(leftR,leftB)+max(rightR,rightB),ans）
ans>=n就说明碰头了 ans=n
不然输出ans。
代码如下：
/* ID:newyear111 PROG: beads LANG: C++ */#include <iostream>
#include <fstream>
#include <cstring>
#include<algorithm>
using namespace std;
const int N=701;string str;
int leftB[N],leftR[N],rightB[N],rightR[N];int main()
{ifstream fin("beads.in");ofstream fout("beads.out");int n; fin>>n;fin>>str;str+=str;for(int i=1;i<=n*2;i++){if(str[i-1]=='b'){leftB[i]=leftB[i-1]+1;}else if(str[i-1]=='r'){leftR[i]=leftR[i-1]+1;}else{leftR[i]=leftR[i-1]+1;leftB[i]=leftB[i-1]+1;}}for(int i=2*n-1;i>=0;i--){if(str[i]=='r'){rightR[i]=rightR[i+1]+1; }else if(str[i]=='b'){rightB[i]=rightB[i+1]+1; }else{rightR[i]=rightR[i+1]+1;rightB[i]=rightB[i+1]+1; }}int ans=0;for(int i=0;i<2*n;i++){ans=max(max(leftR[i],leftB[i])+max(rightR[i],rightB[i]),ans);}if(ans>n)ans=n;fout<<ans<<endl;fin.close();fout.close();return 0;
}