2456 - 破碎的项链
你有一条由<span>N</span>个红色的，白色的，或蓝色的珠子组成的项链<span>(3<=N<=350)</span>，珠子是随意安排的。 这里是 <span>n=29 </span>的二个例子<span>:</span>
1 2 1 2
r b b r b r r b
r b b b
r 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</span></pre>
图片 A 图片 B r 代表 红色的珠子 b 代表 蓝色的珠子 w 代表 白色的珠子
第一和第二个珠子在图片中已经被作记号。
图片 A 中的项链可以用下面的字符串表示：
brbrrrbbbrrrrrbrrbbrbbbbrrrrb .
假如你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事(颜色可能与在这之前收集的不同)。 确定应该在哪里打破项链来收集到最大多数的数目的子。 Example 举例来说，在图片 A 中的项链，可以收集到8个珠子,在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链。 在一些项链中，包括白色的珠子如图片 B 所示。 当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。 表现项链的字符串将会包括三符号 r ， b 和 w 。 写一个程序来确定从一条被供应的项链最大可以被收集珠子数目。
Input
输入包含多组测试数据
| 第 1 行: | N, 珠子的数目 |
| 第 2 行: | 一串度为N的字符串, 每个字符是 r ， b 或 w。 |
Output
单独的一行包含从被供应的项链可以被收集的珠子数目的最大值。
Examples
Input
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
Output
11
Solution C++
#include<stdio.h> #include<malloc.h> int sum1=1,sum2=1,h1=1,h2=1; void find1(int i,char a[],int n,int h1){ int first; if(sum1==n-1) return ; if(i==n-1) first=0; else first=i+1; if(a[i]=='w'&&h1==1) a[i]=a[first]; if(a[i]=='w'&&a[i-1]=='w'&&h1!=1) a[i]=a[first]; if(a[first]=='w') a[first]=a[i]; if(a[i]==a[first]) {sum1++;find1(first,a,n,h1++);} if(a[i]!=a[first]) return; } void find2(int i,char a[],int n,int h2){ int first,last; last=i-1; if(i-1<0) last=n-1; if(sum1+sum2==n) return; if(i==0) first=n-1; else first=i-1; if(a[i]=='w'&&h2==1) a[i]=a[first]; if(a[i]=='w'&&a[last]=='w'&&h1!=1) a[i]=a[first]; if(a[first]=='w') a[first]=a[i]; if(a[i]==a[first]) {sum2++;find2(first,a,n,h2++);} if(a[i]!=a[first]) return; } int main() {int n; while(scanf("%d",&n)!=EOF){ getchar(); int max=2; char *a,*b; a=(char *)malloc(n*sizeof(char)); b=(char *)malloc(n*sizeof(char)); scanf("%s",a); for(int i=0;i<n;i++) b[i]=a[i]; for(int i=0;i<n;i++){ find1(i,a,n,1); if(i>0) find2(i-1,a,n,1); else find2(n-1,a,n,1); if(sum1+sum2>max) max=sum1+sum2; sum1=sum2=h1=h2=1; for(int j=0;j<n;j++) a[j]=b[j]; } printf("%d\n",max); } return 0; }