題目鏈接：http://ace.delos.com/usacoprob2?a=RfmQrEONAFb&S=beads今天開始重做usaco了。上次是去年這個(gè)時(shí)候了，一眨眼一年就過(guò)去了。做了兩個(gè)月才到4.3，后來(lái)就沒(méi)做了。
現(xiàn)在重新開始吧。
beads這題，比較巧妙的地方就是把字符串復(fù)制一份，從而就避免了邊界檢查。
用left[0][i]來(lái)記錄從某一點(diǎn)向左可以收集到的最長(zhǎng)r色beads數(shù)
用left[1][i]來(lái)記錄從某一點(diǎn)向左可以收集到的最長(zhǎng)b色beads數(shù)
right數(shù)組類推。
顯然，如果i為r色，則向左可以收集到的最長(zhǎng)r色為left[0][i-1]+1.可以向左收集到的最長(zhǎng)b色為0。
如果i為b色，類推。
如果i為w色，i即可做r，也可做b.所以各自加1.
代碼如下：
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("beads.in");
ofstream fout("beads.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
//為簡(jiǎn)化代碼，在數(shù)組前后各加1位，這樣i+1,i-1不會(huì)越界，也無(wú)需對(duì)邊界情況特殊處理。
int l[2][702];
int r[2][702];
void solve()
{
int num;
in>>num;
string s;
in>>s;
s+=s;
memset(r,0,sizeof(l));
memset(r,0,sizeof(r));
for(int i=s.size();i>=1;--i){
if(s[i-1]=='r'){
r[0][i] = r[0][i+1]+1;
r[1][i] = 0;
}else if(s[i-1]=='b'){
r[0][i] = 0;
r[1][i] = r[1][i+1]+1;
}else{
r[0][i] = r[0][i+1]+1;
r[1][i] = r[1][i+1]+1;
}
}
for(int i=1;i<=s.size();++i){
if(s[i-1]=='r'){
l[0][i] = l[0][i-1]+1;
l[1][i] = 0;
}else if(s[i-1]=='b'){
l[0][i] = 0;
l[1][i] = l[1][i-1]+1;
}else{
l[0][i] = l[0][i-1]+1;
l[1][i] = l[1][i-1]+1;
}
}
int res = INT_MIN;
for(int i=1;i<=num;++i){
res = max(res, max(r[0][i],r[1][i])+max(l[0][i+num-1],l[1][i+num-1]));
}
// 在出現(xiàn)重疊的情況下，res會(huì)大于num.最大只能是num
res = min(res,num);
out<<res<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}