題目描述

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

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

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

brbrrrbbbrrrrrbrrbbrbbbbrrrrb

假如你要在一些點打破項鏈,展開成一條直線，然后從一端開始收集同顏色的珠子直到你遇到一個不同的顏色珠子，在另一端做同樣的事(顏色可能與在這之前收集的不同)。 確定應該在哪里打破項鏈來收集到最大數目的珠子。

例如，在圖片 A 中的項鏈中，在珠子 9 和珠子 10 或珠子 24 和珠子 25 之間打斷項鏈可以收集到8個珠子。

白色珠子什么意思?

在一些項鏈中還包括白色的珠子(如圖片B) 所示。

當收集珠子的時候，一個被遇到的白色珠子可以被當做紅色也可以被當做藍色。

表現含有白珠項鏈的字符串將會包括三個符號 r ， b 和 w 。

寫一個程序來確定從一條被給出的項鏈可以收集到的珠子最大數目。

輸入輸出格式

輸入格式：

?

第 1 行: N, 珠子的數目

第 2 行: 一串長度為N的字符串, 每個字符是 r ， b 或 w。

?

輸出格式：

?

輸出一行一個整數，表示從給出的項鏈中可以收集到的珠子的最大數量。

?

輸入輸出樣例

輸入樣例#1： 復制 29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb 輸出樣例#1： 復制 11

?

? ? 思路：暴力，破圓為鏈。然后枚舉斷點。一直被一組數組卡，卡了一中午，很無語，后來知道是如果一開始鏈的兩端是白色（w），就需要改變一下端點顏色。

1 #include<bits/stdc++.h> 2 using namespace std; 3 char c[1000]; 4 int main() 5 { 6 int T; 7 8 9 while(cin>>T) 10 { 11 for(int i=1;i<=T;++i)//破圓 12 { 13 cin>>c[i]; 14 c[T+i]=c[i]; 15 } 16 int MAX=-0x7fffffff; 17 for(int i=1;i<=2*T;++i)//枚舉 18 { 19 int num=0; 20 int head=i,tail=i-1; 21 while(c[tail]=='w') tail--;//端點不能為白色 22 char s1=c[tail]; 23 while(c[head]=='w') head++;//端點不能為白色 24 char s=c[head]; 25 tail=i-1;head=i; 26 while(1) 27 { 28 if(head>2*T) break; 29 if(c[head]==s||c[head]=='w') num++; 30 else break; 31 ++head; 32 33 } 34 while(1) 35 { 36 if(tail<1) break; 37 if(c[tail]==s1||c[tail]=='w') num++; 38 else break; 39 tail--; 40 41 } 42 43 MAX=max(MAX,num); 44 } 45 cout<<min(MAX,T)<<endl;//最大就是珠子的個數 46 } 47 } View Code

?

轉載于:https://www.cnblogs.com/Auroras/p/10862665.html

總結

以上是生活随笔為你收集整理的坏掉的项链Broken Necklace的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。