P1203 [USACO1.1]坏掉的项链Broken Necklace
斯德哥尔摩
2018-10-20 21:13:36
[P1203 [USACO1.1]坏掉的项链Broken Necklace](https://www.luogu.org/problemnew/show/P1203)
真·模拟题。。。
然而坑点贼多。。。
首先断环成链再倍长没的说。
然后枚举断点,暴力搜索能取走的珠子。
统计下答案就好。
注意:
1. 可能断点的左边或右边的起始会有连续的白色珠子,直接特判掉即可。
2. 每个珠子只能取一次!不要问我是怎么知道的。。。
唉,这种沙茶模拟题我竟然还能$WA\times 1$。。。
感觉自己是个$ZZ$。。。
附代码:
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 710
using namespace std;
int n,ans=0;
char str[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
for(int l=1,r=n;l<=n;l++,r++){
int i=l,j=r,s=0;
char left,right;
while(i<=r&&str[i]=='w'){i++;s++;}
left=str[i];
while(j>=l&&str[j]=='w'){j--;s++;}
right=str[j];
while(i<=r&&(str[i]==left||str[i]=='w')){i++;s++;}
while(j>=l&&(str[j]==right||str[j]=='w')){j--;s++;}
if(s>n)s=n;
ans=max(ans,s);
}
printf("%d\n",ans);
}
void init(){
n=read();
scanf("%s",str+1);
for(int i=1;i<=n;i++)str[i+n]=str[i];
}
int main(){
init();
work();
return 0;
}
```