Broken Necklace
破碎的項(xiàng)鏈
譯 by timgreen
你有一條由N個(gè)紅色的，白色的，或藍(lán)色的珠子組成的項(xiàng)鏈(3<=N<=350)，珠子是隨意安排的。 這里是 n=29 的二個(gè)例子:
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 代表 藍(lán)色的珠子
w 代表 白色的珠子
第一和第二個(gè)珠子在圖片中已經(jīng)被作記號。?
圖片 A 中的項(xiàng)鏈可以用下面的字符串表示：?
brbrrrbbbrrrrrbrrbbrbbbbrrrrb .?
假如你要在一些點(diǎn)打破項(xiàng)鏈,展開成一條直線，然后從一端開始收集同顏色的珠子直到你遇到一個(gè)不同的顏色珠子，在另一端做同樣的事。(顏色可能與在這之前收集的不同) 確定應(yīng)該在哪里打破項(xiàng)鏈來收集到最大多數(shù)的數(shù)目的子。 Example 舉例來說，在圖片 A 中的項(xiàng)鏈，可以收集到8個(gè)珠子,在珠子 9 和珠子 10 或珠子 24 和珠子 25 之間打斷項(xiàng)鏈。 在一些項(xiàng)鏈中，包括白色的珠子如圖片 B 所示。 當(dāng)收集珠子的時(shí)候，一個(gè)被遇到的白色珠子可以被當(dāng)做紅色也可以被當(dāng)做藍(lán)色。 表現(xiàn)項(xiàng)鏈的字符串將會包括三符號 r ， b 和 w 。 寫一個(gè)程序來確定從一條被供應(yīng)的項(xiàng)鏈最大可以被收集珠子數(shù)目。?
PROGRAM NAME: beads
INPUT FORMAT?
|
第 1 行:
|
N, 珠子的數(shù)目?
|
|
第 2 行:
|
一串度為N的字符串, 每個(gè)字符是 r ， b 或 w。?
|
SAMPLE INPUT (file beads.in)?
29?
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb?
OUTPUT FORMAT?
單獨(dú)的一行包含從被供應(yīng)的項(xiàng)鏈可以被收集的珠子數(shù)目的最大值。?
SAMPLE OUTPUT (file beads.out)?
11
由于整個(gè)珠子連起來是一個(gè)項(xiàng)鏈，也就是一個(gè)環(huán)。我在讀入數(shù)據(jù)以后在一個(gè)數(shù)組里吧整個(gè)項(xiàng)鏈連續(xù)存了3遍。然后我從中間的一組數(shù)據(jù)中枚舉斷開點(diǎn)，向兩邊擴(kuò)展。剩下的算就行了
#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);
}