[USACO1.1]坏掉的项链Broken Necklace
方法一：很容易想到枚举断点，再分别两头找，但是要注意很多细节
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
string s;
int n,l,r,ll,rr,tmp,ans;
inline int calc(int x) {
ll=s[x],rr=s[x+1],l=x-1,r=x+2;
if (rr=='w') {//如果是w，需分类讨论（如10 rwrwbwrwrw，答案为10，去掉后输出9）
rr='r',tmp=x+2;
while((s[tmp]=='w' || s[tmp]==rr) && tmp<x+n) tmp++;
rr='b';
}
while((s[l]=='w' || s[l]==ll) && l>x-n) l--;
while((s[r]=='w' || s[r]==rr) && r<x+n) r++;
return max(r,tmp)-l-1;
}
int main() {
cin>>n>>s;
s=s+s+s;
for (int i=n; i<n+n; i++)//复制了三段，从中间一段枚举断点
if (s[i]!=s[i+1] && s[i]!='w')//当s[i]==s[i+1]时，在i+1计算比在i更优
ans=max(ans,calc(i));
if (s[n+n-1]==s[n+n]) ans=max(ans,calc(n+n-1));//如果都是同一颜色，则最后一个答案没有计算（如3 rrr，去掉min答案就变成0）
printf("%d",min(ans,n));//如果都是同一颜色，则结果不应超过n，（如3 rrr，去掉min答案就变成5）
}
方法二：一边做一边统计答案（思路来自这个博客）
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
char s[700],c;
int n,l,r,w,ans;
/*
l:左段长度，r：右段长度
w:连续w段的长度
c:当前段的颜色
*/
int main() {
scanf("%d%s",&n,s);
memcpy(s+n,s,n);
for (int i=0; i<n<<1; i++)
if (s[i]=='w') w++,r++;
else if (s[i]==c) w=0,r++;
else ans=max(ans,l+r),l=r-w,r=w+1,w=0,c=s[i];
//这里不能写为l=r,r=1，要把w段给右边，这样在下次修改答案时l更大
//如：bwrrb，遇到第一个r时应当把w给右边，即l=r-w=1,r=w+1=2,这样到第二个b时l更新为3
//而如果用l=r=2,r=1, 第二个b时l更新为2（把开头的w舍去了）
printf("%d",min(max(ans,l+r),n));
}
方法三：dp（思路来自这个博客）
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,lb[701],lr[701],rb[701],rr[701],ans;//l[i]不包括i，r[i]包括i
char s[701];
int main() {
scanf("%d%s",&n,s),memcpy(s+n,s,n),n<<=1;
for (int i=1; i<n; i++)
if (s[i-1]=='b') lb[i]=lb[i-1]+1;
else if (s[i-1]=='r') lr[i]=lr[i-1]+1;
else lb[i]=lb[i-1]+1,lr[i]=lr[i-1]+1;
for (int i=n-2; i>=0; i--)
if (s[i]=='b') rb[i]=rb[i+1]+1;
else if (s[i]=='r') rr[i]=rr[i+1]+1;
else rb[i]=rb[i+1]+1,rr[i]=rr[i+1]+1;
for (int i=0; i<n; i++)
ans=max(ans,max(lb[i],lr[i])+max(rb[i],rr[i]));
printf("%d",min(ans,n>>1));
}