Broken Necklace

破碎的項鏈

譯 by timgreen

你有一條由N個紅色的，白色的，或藍色的珠子組成的項鏈(3<=N<=350)，珠子是隨意安排的。 這里是 n=29 的二個例子: 

				
						
              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
              圖片 A                          圖片  B
                 
                  r 代表 紅色的珠子      
                     b 代表 藍色的珠子   
                     w 代表 白色的珠子

第一和第二個珠子在圖片中已經被作記號。?

圖片 A 中的項鏈可以用下面的字符串表示：?

brbrrrbbbrrrrrbrrbbrbbbbrrrrb .?

假如你要在一些點打破項鏈,展開成一條直線，然后從一端開始收集同顏色的珠子直到你遇到一個不同的顏色珠子，在另一端做同樣的事。(顏色可能與在這之前收集的不同) 確定應該在哪里打破項鏈來收集到最大多數的數目的子。 Example 舉例來說，在圖片 A 中的項鏈，可以收集到8個珠子,在珠子 9 和珠子 10 或珠子 24 和珠子 25 之間打斷項鏈。 在一些項鏈中，包括白色的珠子如圖片 B 所示。 當收集珠子的時候，一個被遇到的白色珠子可以被當做紅色也可以被當做藍色。 表現項鏈的字符串將會包括三符號 r ， b 和 w 。 寫一個程序來確定從一條被供應的項鏈最大可以被收集珠子數目。?

PROGRAM NAME: beads

INPUT FORMAT?

第 1 行: N, 珠子的數目?
第 2 行: 一串度為N的字符串, 每個字符是 r ， b 或 w。?

SAMPLE INPUT (file beads.in)?

29?

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb?

OUTPUT FORMAT?

單獨的一行包含從被供應的項鏈可以被收集的珠子數目的最大值。?

SAMPLE OUTPUT (file beads.out)?

11


由于整個珠子連起來是一個項鏈，也就是一個環(huán)。我在讀入數據以后在一個數組里吧整個項鏈連續(xù)存了3遍。然后我從中間的一組數據中枚舉斷開點，向兩邊擴展。剩下的算就行了

#include?"stdlib.h"
#include?"stdio.h"
#define?N?350*3+30
char?s[N];
int?n;

void?input()
{
????int?i;
????scanf("%d",&n);
????getchar();
????scanf("%s",s);
????for(i=0;i<n;i++)
????{
????????s[i+n]=s[i+n+n]=s[i];
????}
}

int?getbeans(int?l,int?r)
{
????int?i=l,j=r;
????int?f1=0,f2=0;
????while(i>=0)
????{
????????if(s[i]!='w'&&s[l]=='w')
????????????l=i;
????????if(s[i]==s[l]||s[i]=='w')
????????????f1++;
????????else
????????????break;
????????i--;
????}
????while(j<=3*n-1)
????{
????????if(s[r]=='w'&&s[j]!='w')
????????????r=j;
????????if(s[j]==s[r]||s[j]=='w')
????????????f2++;
????????else
????????????break;
????????j++;
????}
????if(f1+f2>=n)
????????return?n;
????else
????????return?f1+f2;
}

int?work()
{
????int?i;
????int?got=0;
????int?ans=0,t;
????for(i=n;i<2*n;i++)
????{
????????if(s[i]!=s[i+1])
????????{
????????????got++;
????????????t=getbeans(i,i+1);
????????????ans=ans>t?ans:t;

????????}
????}
????if(got)
????????return?ans;
????else
????????return?n;
}

int?main()
{
????freopen("beads.in","r",stdin);
????freopen("beads.out","w",stdout);
????input();
????printf("%d\n",work());
????exit(0);
}