【問(wèn)題描述】
你有一條由N個(gè)紅色的、白色的、或藍(lán)色的珠子組成的項(xiàng)鏈，珠子是隨意安排的。下面是 N=29 的兩個(gè)項(xiàng)鏈：其中’r’代表 紅色的珠子，’b’代表藍(lán)色的珠子，’w’代表白色的珠子，項(xiàng)鏈中的第一和第二個(gè)珠子已經(jīng)被作記號(hào)。比如圖片 A 中的項(xiàng)鏈可以表示為：brbrrrbbbrrrrrbrrbbrbbbbrrrrb。 假如你要在一些點(diǎn)打破項(xiàng)鏈,展開(kāi)成一條直線，然后從一端開(kāi)始收集同顏色的珠子直到你遇到一個(gè)不同的顏色珠子，在另一端做同樣的事(顏色可能與在這之前收集的不同)。 確定應(yīng)該在哪里打破項(xiàng)鏈來(lái)收集到最大數(shù)目的珠子。例如，在圖片 A 中的項(xiàng)鏈中，在珠子 9 和珠子 10 或珠子 24 和珠子 25 之間打斷項(xiàng)鏈可以收集到8個(gè)珠子。在一些項(xiàng)鏈中還包括白色的珠子(如圖片B)所示。當(dāng)收集珠子的時(shí)候，一個(gè)被遇到的白色珠子可以被當(dāng)做紅色也可以被當(dāng)做藍(lán)色。寫一個(gè)程序來(lái)確定從一條被給出的項(xiàng)鏈可以收集到的珠子最大數(shù)目。
【輸入格式】
第 1 行: N, 珠子的數(shù)目 第 2 行: 一串長(zhǎng)度為N的字符串, 每個(gè)字符是 r ， b 或 w。
【輸出格式】
單獨(dú)的一行包含從被供應(yīng)的項(xiàng)。
【輸入樣例】
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
【輸出樣例】
11
【數(shù)據(jù)范圍】
3 <= N <= 350 【分析】 用數(shù)組bl,br,rl,rr分別記錄在項(xiàng)鏈i處向左向右收集的籃色紅色珠子數(shù)。 項(xiàng)鏈?zhǔn)黔h(huán)形的，但我們只要把兩個(gè)同樣的項(xiàng)鏈放在一塊，就把它轉(zhuǎn)換成線性的了【破環(huán)】。 補(bǔ)充：對(duì)w我們只需將它看成斗地主中的癩子即可，隨便用 我們只要求出bl,br,rl,rr，那么結(jié)果就為 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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
