【USACO1.1】Broken Necklace

題意

一個環形項鏈，有rbw三種珠子，r代表red，b代表blue，w代表white，從任意一個位置斷開，兩端分別取珠子，同一端取的珠子要相同顏色，w可以染成想要的顏色，即既可當作r也可以當作b，求最多取得的珠子個數。最多有350個珠子。

分析

可以枚舉斷開的位置，然后模擬取珠子。也可以枚舉起點位置。還可以dp做。

代碼

枚舉斷點

#include<cstdio>
#include<algorithm>
#define N 355
using namespace std;

char a;
int b[N];
int n,ans;

int solve(int p,int dir) //p為起始點，dir為方向，求最多取幾顆
{
int len=0;//取了的珠子個數，最多取n顆珠子

for(int j=p+n; len<n; len++,j+=dir) //j為當前位置+n，當前位置為j%n
    {
if(b[p] && b[j%n] && b[j%n]!=b[p])
break;
if(!b[p])//每次取珠子都要符合p位置的顏色，若p位置是w，就要更新p
            p=j%n;
    }
return len;
}
int main()
{
scanf("%d ",&n);
for(int i=0; i<n; i++)
    {
        a=getchar();
        b[i]=a=='b'?1:a=='r'?2:0;// b--1 r--2 w--0
    }
for(int i=0; i<n; i++)//枚舉斷點
        ans=max(ans,solve(i,-1)+solve(i+1,1));
    ans=min(ans,n);//可能同一顆被兩次計算過，但只出現在全都取的情況里
printf("%d\n",ans);
return 0;
}

枚舉起點

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int n,ans;
string s;
int main()
{
cin>>n>>s;
    s+=s;
for(int i=0,j; i<n; i++) //以i為第一段的起點，不是切開的位置
    {
char now=s[i];
int len=0;
int times=now=='w'?3:2;//如果當前是白色，那么需要找三段相同顏色的否則找兩段
        j=i;
while(times--)
        {
while(j<i+n&&(s[j]==now||s[j]=='w'))
            {
                len++;
                j++;
            }
            now=s[j];
        }
        ans=max(ans,len);
    }
cout<<ans<<endl;
return 0;
}

DP

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#define N 720
using namespace std;
int n,ans;
string s;
int l[N][2],r[N][2];
int main(){
cin>>n>>s;
    s+=s;
for(int i=1;i<2*n;i++){
        l[i][0]=l[i-1][0]+1;
        l[i][1]=l[i-1][1]+1;
if(s[i-1]=='r')
            l[i][1]=0;
else if(s[i-1]=='b')
            l[i][0]=0;
    }
for(int i=2*n-1;i>=0;i--){
        r[i][0]=r[i+1][0]+1;
        r[i][1]=r[i+1][1]+1;
if(s[i]=='r')
            r[i][1]=0;
else if(s[i]=='b')
            r[i][0]=0;
    }
for(int i=0;i<2*n;i++)
        ans=max(ans,max(l[i][0],l[i][1])+max(r[i][0],r[i][1]));
    ans=min(ans,n);
cout<<ans<<endl;
return 0;
}