• 題目
• 題目分析
• 推的過(guò)程
• 需要避免的坑
• 整體代碼
• USACO的題解

題目

題目描述

輸入描述

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

輸出描述

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

樣例輸入

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

樣例輸出

11

題目分析

考慮到循環(huán)的情況，簡(jiǎn)單起見(jiàn)，直接把這個(gè)輸入的字符串變成三個(gè)串黏在一起?？紤]的串的范圍是s[n]~s[2*n-1]
實(shí)際上就是求出每個(gè)點(diǎn)如是切下去，往左和往右各能延伸多少，取一個(gè)最大值。本題數(shù)據(jù)不是特別大，可能暴力并非不可能，我沒(méi)有嘗試。我的想法是一個(gè)個(gè)推出來(lái)。以ans[0][i]表示在第i的節(jié)點(diǎn)左邊切下去，那么左邊切口最長(zhǎng)能延展多少；以ans[1][i]表示在第i的節(jié)點(diǎn)右邊切下去，那么右邊切口最長(zhǎng)能延展多少。

推的過(guò)程

此處以ans[0][i]為例講解。
首先第一個(gè)點(diǎn)ans[0][n]的求解:
先把s[n]左邊所有的通用顏色w讀掉并且記錄數(shù)字，接著記錄第一個(gè)出現(xiàn)的顏色字符到dif里面，接著繼續(xù)往左掃，遇到w時(shí)長(zhǎng)度顯然是變長(zhǎng)的（變色），遇到和dif內(nèi)顏色相同的也顯然變長(zhǎng)，當(dāng)遇到不一樣的顏色時(shí)就中止，此時(shí)的最長(zhǎng)長(zhǎng)度就是ans[0][n]
接著往右邊推了。請(qǐng)看我的靈魂作圖

從左往右推的過(guò)程中，需要記錄出現(xiàn)的最后一個(gè)非w字母是哪個(gè)字母，記在dif里面，wn記錄連續(xù)出現(xiàn)了多少個(gè)w
當(dāng)推到第i個(gè)位置的時(shí)候
如果i是w的話，那么直接s[i]=s[i-1]+1（因?yàn)榭梢宰兩ど?#xff09;，之后wn++
如果i不是w且和dif相同的話，那么顯然仍然是s[i]=s[i-1]+1 （中間的w變色成和他們一樣）
如果i不是w且和dif不同的話，那s[i]=wn+1 （一串w變色成和i一樣）
注意，在第二和第三種情況下，需要將wn置零并且更新dif是哪個(gè)顏色

需要避免的坑

注意，若是只有通用顏色w和其中某一種顏色比如說(shuō)r的話，就會(huì)變成這樣
wwbbbb
那么在最左邊切開(kāi)的話，往左往右最長(zhǎng)都能延展6個(gè)長(zhǎng)度，那么加起來(lái)的和就是12了，都超過(guò)串的總長(zhǎng)了
另一種情況例如
wwbbrr，那么從bb rr這里切開(kāi)的話，bb往左結(jié)合兩個(gè)w長(zhǎng)度變?yōu)?，rr往右結(jié)合兩個(gè)w長(zhǎng)度變?yōu)?，因此長(zhǎng)度是8，也超過(guò)總長(zhǎng)了。
這兩種情況的最優(yōu)解顯然都是所有珠子都可以取到，因此若出現(xiàn)最大可能超過(guò)數(shù)量n的情況，答案就是n沒(méi)錯(cuò)了

整體代碼

/* ID: penguin14 PROG: beads LANG: C++ */ #include<iostream> #include <fstream> #include<algorithm> #include<cstring> #include<string> using namespace std; string s; int ans[2][355*3]; int main() {ofstream fout("beads.out");ifstream fin("beads.in");int n, r, b, i;int cnt;int wn,maxx;char dif;bool flag;while (fin >> n) {flag = true;fin >> s;s = s + s + s;ans[0][n] = 1;i = n - 1;while (s[i] == 'w') {ans[0][n]++;i--;}dif = s[i];if (i != n - 1)s[n-1] = dif;for (i--;i>=0; --i) {if (s[i] == dif || s[i] == 'w') {ans[0][n]++;}else {break;}}ans[1][2*n-1] = 1;i = 2*n-1;while (s[i] == 'w') {ans[1][2*n-1]++;i++;}dif = s[i];if(i!=2*n-1)s[2*n-1]=dif;for(i++;i<3*n;++i){if(s[i]==dif||s[i]=='w'){ans[1][2*n-1]++;}else{break;}}wn = 0;dif = s[n-1];for(int i=n+1;i<2*n;++i){if(s[i-1]=='w'){wn++;ans[0][i]=ans[0][i-1]+1;}else{if(s[i-1]==dif){ans[0][i]=ans[0][i-1]+1;}else{ans[0][i]=wn+1;}wn=0;dif=s[i-1];}}wn=0;dif = s[2*n-1];for(int i=2*n-2;i>=n;--i){if(s[i]=='w'){wn++;ans[1][i]=ans[1][i+1]+1;}else{if(s[i]==dif){ans[1][i]=ans[1][i+1]+1;}else{ans[1][i]=wn+1;}wn=0;dif=s[i];}}maxx=ans[0][n]+ans[1][n];for(int a=n+1;a<2*n;a++){maxx=max(maxx,ans[0][a]+ans[1][a]);if(maxx>=n){fout<<n<<endl;flag = false;break;}}if(flag)fout<<maxx<<endl;}return 0; }

USACO的題解

USACO指出我這個(gè)實(shí)際上是dp的做法
另外，最簡(jiǎn)單的版本，暴力是可行的

總結(jié)

以上是生活随笔為你收集整理的USACO Section 1.2 Broken Necklace的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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