題目描述
你有一條由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
說明
題目翻譯來自NOCOW。

USACO Training Section 1.1

垃圾題，水題，超級好想，大家都去做！！?
這個題，因為數據不大可以枚舉，也可以DP，我騙數據過的，稍微修改一下就不用騙數據了！

#include<cstdio> #include<iostream> using namespace std; int main() {int n,t;cin>>n;string a;cin>>a;a=a+a+a;int r,b,sum=0;for(int i=a.length()/3;i<2*a.length()/3;i++){r=b=0;char z1=a[i];t=i;while(z1=='w') {z1=a[--t];}char z2=a[i+1];t=i+1;while(z2=='w') {z2=a[++t];}for(int j=i;j>a.length()/3;j--){if(a[j]!=z1&&a[j]!='w') break;else r++;// cout<<a[j]<<' ';}for(int j=i+1;j<a.length()/3*2+a.length();j++){if(a[j]!=z2&&a[j]!='w') break;else r++;// cout<<a[j]<<' ';}sum=max(sum,r);}if(sum>n)cout<<n<<endl; else cout<<sum<<endl; }

總結

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

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