USACO broken necklace 破碎的項鍊

QUESTION

You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for 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
        Figure A                         Figure B
                    r red bead
                    b blue bead
                    w white bead
           

The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b’s and r’s, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).

Determine the point where the necklace should be broken so that the most number of beads can be collected.

EXAMPLE

For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.

In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration can include any of the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.

PROGRAM NAME: beads

INPUT FORMAT

Line 1: N, the number of beads

Line 2: a string of N characters, each of which is r, b, or w

SAMPLE INPUT (file beads.in)

29

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

OUTPUT FORMAT

A single line containing the maximum of number of beads that can be collected from the supplied necklace.

SAMPLE OUTPUT (file beads.out)

11

OUTPUT EXPLANATION

Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.

Two necklace copies joined here

v

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb|wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

*|

rrrrrb|bbbbb <-- assignments

5xr …#|##### 6xb

5+6 = 11 total

題目描述

你有一條由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

解題思路：

1.純暴力

2.按照順序一個一個點做，将那個點作為第一個點，後面的作為第二，第三。。。個點。也就是重新排序。這樣可以友善很多。

3.如果左邊第一個點時‘w’時先不判斷，用一個tmp儲存第一個不是‘w’的點，将那個點的字元作為tmp，之後每一個隻要是tmpl就加一

4.從左往右搜。

5.如果右邊第一個點時‘w’時先不判斷，用一個tmp儲存第一個不是‘w’的點，将那個點的字元作為tmp，之後每一個隻要是tmpr就加一

6.從右往左搜。

7.int sum=l+r

8.if(sum>ans){ ans=sum; }

9.如果加起來大于輸入的n，就直接輸出n，else輸出ans即可

代碼：

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
//freopen("beads.in","r",stdin);
//freopen("beads.out","w",stdout);
char bead[500];
int n;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){ 
cin>>bead[i];
}
char bead1[500];
for(int i=0;i<n;i++){
bead1[i]=bead[i];
}
int l=0,r=0;
for(int i=0;i<n;i++){
l=0;
r=0;
for(int j=0;j<n;j++){
bead[(i+j)%n]=bead1[j];
}
//l
char ltmp='s';
int cnt=0;
for(int j=0;j<n;j++){
if(bead[j]=='w'){
l++;
}else{
cnt=j;
ltmp=bead[j];
break;
}
}
for(int j=cnt;j<n;j++){ 
if(ltmp==bead[j]||bead[j]=='w')
{ 
l++; 
}
else{ 
break; 
} 
} 

//r 
char rtmp='s'; 
cnt=0; 
for(int j=n-1;j>=0;j--){
if(bead[j]=='w'){
r++;
}else{
cnt=j;
rtmp=bead[j];
break;
}
}
for(int j=cnt;j>=0;j--){
if(rtmp==bead[j]||bead[j]=='w'){
r++;
}else{
break;
}
}
int sum=l+r;
if(sum>ans){
ans=sum;
}
}
if(ans>n){
ans=n;
}
cout<<ans<<endl;
return 0;
}