动态规划。 设bl, br, rl, rr 分别为项链 i 处向左、向右收集到蓝色、红色珠子数。项链是环形的，只要把两个同样的项链放在一起，则转换成线性。
bl[0] = rl[0] = 0
if necklace[i] = 'r' rl[i]=rl[i-1]+1, bl[i]=0;
if necklace[i] = 'b' bl[i]=bl[i-1]+1, rl[i] = 0;
if necklace[i] = 'w' rl[i] = rl[i-1]+1, bl[i]=bl[i-1]+1
result = max( max(bl[i], rl[i] ) + max(br[i+1], rr[i+1]) ) (0<= i <= 2*n -1)
/**//*
ID: lorelei3
PROG: beads
LANG: C++
*/
#include <fstream>
#include <string>
#include <iostream>
using namespace std;
int main()
{
string s;
int max=0,len;
ifstream in("beads.in");
ofstream out("beads.out");
in>>len>>s;
s+=s;
len+=len;
for(int i=0; i<len-1; ++i){
int leftIndex=i, rightIndex=i+1;
char leftColor=s[leftIndex], rightColor=s[rightIndex];
while((leftIndex-1)>=0){
leftIndex--;
if(s[leftIndex]=='w')
continue;
else{
if(leftColor=='w'){
leftColor=s[leftIndex];
continue;
}else if(leftColor==s[leftIndex]){
continue;
}else{
leftIndex++;
break;
}
}
}
while((rightIndex+1)<len){
rightIndex++;
if(s[rightIndex]=='w')
continue;
else{
if(rightColor=='w'){
rightColor=s[rightIndex];
continue;
}else if(rightColor==s[rightIndex]){
continue;
}else{
rightIndex--;
break;
}
}
}
max = max>(rightIndex-leftIndex)? max : (rightIndex-leftIndex);
}
if(max+1>len/2)
out<<len/2<<endl;
else
out<<max+1<<endl;
return 0;
}posted on 2010-11-04 21:30
小阮 阅读(541)
评论(0) 编辑 收藏 引用 所属分类:
USACO