【問題描述】
你有一條由N個紅色的、白色的、或藍色的珠子組成的項鏈，珠子是隨意安排的。下面是 N=29 的兩個項鏈：其中’r’代表 紅色的珠子，’b’代表藍色的珠子，’w’代表白色的珠子，項鏈中的第一和第二個珠子已經(jīng)被作記號。比如圖片 A 中的項鏈可以表示為：brbrrrbbbrrrrrbrrbbrbbbbrrrrb。 假如你要在一些點打破項鏈,展開成一條直線，然后從一端開始收集同顏色的珠子直到你遇到一個不同的顏色珠子，在另一端做同樣的事(顏色可能與在這之前收集的不同)。 確定應該在哪里打破項鏈來收集到最大數(shù)目的珠子。例如，在圖片 A 中的項鏈中，在珠子 9 和珠子 10 或珠子 24 和珠子 25 之間打斷項鏈可以收集到8個珠子。在一些項鏈中還包括白色的珠子(如圖片B)所示。當收集珠子的時候，一個被遇到的白色珠子可以被當做紅色也可以被當做藍色。寫一個程序來確定從一條被給出的項鏈可以收集到的珠子最大數(shù)目。
【輸入格式】
第 1 行: N, 珠子的數(shù)目 第 2 行: 一串長度為N的字符串, 每個字符是 r ， b 或 w。
【輸出格式】
單獨的一行包含從被供應的項。
【輸入樣例】
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
【輸出樣例】
11
【數(shù)據(jù)范圍】
3 <= N <= 350 【分析】 用數(shù)組bl,br,rl,rr分別記錄在項鏈i處向左向右收集的籃色紅色珠子數(shù)。 項鏈是環(huán)形的，但我們只要把兩個同樣的項鏈放在一塊，就把它轉換成線性的了【破環(huán)】。 補充：對w我們只需將它看成斗地主中的癩子即可，隨便用 我們只要求出bl,br,rl,rr，那么結果就為 max(max(bl[i],rl[i])+max(br[i+1],rr[i+1])) (0<=i<=2*n-1)
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath>using namespace std;int n,ok=0;char a[400],b[800];int bl[800],br[800],rl[800],rr[800];int max_;void run(){ bl[0]=rl[0]=0;//從左到右 for(int i=1;i<=2*n-1;i++) { if(b[i]=='r') rl[i]=rl[i-1]+1,bl[i]=0; if(b[i]=='b') bl[i]=bl[i-1]+1,rl[i]=0; if(b[i]=='w') bl[i]=bl[i-1]+1,rl[i]=rl[i-1]+1; } br[2*n-1]=rr[2*n-1]=0;//從右到左 for(int i=2*n-2;i>=0;i--) { if(b[i]=='r') rr[i]=rr[i+1]+1,br[i]=0; if(b[i]=='b') br[i]=br[i+1]+1,rr[i]=0; if(b[i]=='w') br[i]=br[i+1]+1,rr[i]=rr[i+1]+1; } }int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); scanf("%s",a); strcpy(b,a); strcat(b+1,a); run(); for(int i=0;i<2*n;i++) { max_=max(max_,max(bl[i],rl[i])+max(br[i+1],rr[i+1])); if(max_>n) max_=n; } for(int i=0;i<2*n;i++) { if(b[i]=='w') continue; else {ok=1;break;} } if(ok==1) cout<<max_; else cout<<n; return 0;}新聞熱點
疑難解答
