随笔-141  评论-9  文章-3  trackbacks-0
动态规划。 设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 小阮 阅读(539) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理