題目描述

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

第一和第二個(gè)珠子在圖片中已經(jīng)被作記號(hào)。
圖片 A 中的項(xiàng)鏈可以用下面的字符串表示：
brbrrrbbbrrrrrbrrbbrbbbbrrrrb

假如你要在一些點(diǎn)打破項(xiàng)鏈,展開成一條直線，然后從一端開始收集同顏色的珠子直到你遇到一個(gè)不同的顏色珠子，在另一端做同樣的事(顏色可能與在這之前收集的不同)。 確定應(yīng)該在哪里打破項(xiàng)鏈來收集到最大數(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)色。

表現(xiàn)含有白珠項(xiàng)鏈的字符串將會(huì)包括三個(gè)符號(hào) r ， b 和 w 。
寫一個(gè)程序來確定從一條被給出的項(xiàng)鏈可以收集到的珠子最大數(shù)目。

輸入輸出格式

輸入格式：
第 1 行: N, 珠子的數(shù)目
第 2 行: 一串長度為N的字符串, 每個(gè)字符是 r ， b 或 w。

輸出格式：
輸出一行一個(gè)整數(shù)，表示從給出的項(xiàng)鏈中可以收集到的珠子的最大數(shù)量。

輸入輸出樣例

輸入樣例#1：
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

輸出樣例#1：
11

說明
題目翻譯來自NOCOW。
USACO Training Section 1.1
.
.
.
.
.
.
.

分析

設(shè)置兩個(gè)指針一個(gè)向左走一個(gè)向右走
要注意：遇到兩個(gè)左右兩個(gè)值都是w 的情況
.
.
.
.
.
.
.

程序：

#include<iostream> using namespace std; int main() {int n;char a[1000];int b[10001];cin>>n;cin>>a;for (int j=n;j<n*2;j++)a[j]=a[j-n];int mx=0;for (int j=0;j<2*n;j++){int l=j,r=j+1;char la=a[l];char ra=a[r];if (a[l]=='w'){ la=a[l-1];}if (a[r]=='w'){ra=a[r-1];}int ans=0;while (l>=0){if (a[l]==la||a[l]=='w') ans++;else break;l--;}while (r<2*n){if (a[r]==ra||a[r]=='w') ans++;else break;r++;}mx=max(mx,ans);}if (mx>n) mx=n; cout<<mx<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499964.html

總結(jié)

以上是生活随笔為你收集整理的[USACO1.1]坏掉的项链Broken Necklace的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。