Home > Old Blog Posts > USACO 1.1.4 Broken Necklace

USACO 1.1.4 Broken Necklace


对初学者来说这是usaco的第一个噩梦。。

算是1.1模拟题中的一道坎吧,但只要细心做,也没有什么难点。

可直接按照题目枚举切断点,也可以采取dp或记忆化搜索(这2种做法详见nocow)。

代码:

/*
ID: dementr1
PROG: beads
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
int bead[1000];
ifstream fin(“beads.in”);
ofstream fout(“beads.out”);
int calc(int i, int bead[], int length)
{
int now=i;
int ans1=0;
int color;
bool sure=false;
while(1)
{
if(sure&&bead[now]!=0&&bead[now]!=color) break;
if(!sure&&bead[now]!=0)
{
sure=true;
color=bead[now];
}
ans1++;
if(ans1>length) return length;
now–;
if(now<0)  now=length-1;
}
now=i+1;
if(now>=length) now=0;
int ans2=0;
sure=false;
while(1)
{
if(sure&&bead[now]!=0&&bead[now]!=color) break;
if(!sure&&bead[now]!=0)
{
sure=true;
color=bead[now];
}
ans2++;
if(ans2>length) return length;
now++;
if(now>=length)  now=0;
}
if(ans1+ans2>length) return length;
else return ans1+ans2;
}
int main()
{
string str;
int length,i,tmp,ans=-1;
fin>>length>>str;
for(i=0;i<length;i++)
{
if(str[i]==’w’) bead[i]=0;
else if(str[i]==’b’) bead[i]=1;
else if(str[i]==’r’) bead[i]=2;
}
for(i=0;i<length;i++)
{
tmp=calc(i,bead,length);
if(tmp>ans) ans=tmp;
}
fout<<ans<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: