[洛谷 1203]Broken Necklace

题目链接

https://www.luogu.org/problemnew/show/P1203

题解

采用断环为链的思想,先将链复制一遍粘在串末尾。

然后枚举切断点的位置,模拟取珠子的过程即可。

如果遇到白色珠子,贪心地将它的颜色视为上一个珠子的颜色即可。(如果是第一个,就视为下一个非白色珠子的颜色)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[705];
int main()
{
 int n,ans=0;
 scanf("%d",&n);
 scanf("%s",s+1);
 for(int i=n+1;i<=2*n;i++)
  s[i]=s[i-n];
 for(int i=1;i<=2*n;i++)
 {
  int l=i,r=i+1,res=0;
  char lc=s[l],rc=s[r];
  while(l>0&&lc=='w')
   lc=s[--l],res++;
  while(r<=2*n&&lc=='w')
   rc=s[++r],res++;
  while(l>0&&(s[l]==lc||s[l]=='w'))
   res++,l--;
  while(r<=2*n&&(s[r]==rc||s[r]=='w'))
   res++,r++;
  ans=max(ans,res);
 }
 printf("%d\n",min(ans,n));
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注