传送门
分析
首先涉及到环形问题的时候,我们常用的解决方法就是开两倍空间把这个环给储存下来
然后我们可以正着反正扫一遍,记录每一种颜色的珠子的最长前缀和最长后缀,最后再扫描一下答案即可
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e3 + 10;
string str;
int n;
int bl[N];
int br[N];
int rl[N];
int rr[N];
int main(){
scanf("%d",&n);
cin >> str;
str = str + str;
// if(str[0] == 'b') bl[0] = 1;
// if(str[0] == 'r') rl[0] = 1;
// if(str[0] == 'w') rl[0] = 1,bl[0] = 1;
for(int i = 0;i < n * 2;i++){
if(str[i] == 'b')
bl[i] = bl[i - 1] + 1,rl[i] = 0;
if(str[i] == 'r')
rl[i] = rl[i - 1] + 1,bl[i] = 0;
if(str[i] == 'w')
bl[i] = bl[i - 1] + 1,rl[i] = rl[i - 1] + 1;
}
for(int i = n * 2 - 1;i >= 0;i--){
if(str[i] == 'b')
br[i] = br[i + 1] + 1,rr[i] = 0;
if(str[i] == 'r')
rr[i] = rr[i + 1] + 1,br[i] = 0;
if(str[i] == 'w')
br[i] = br[i + 1] + 1,rr[i] = rr[i + 1] + 1;
}
int ans = 0;
for(int i = 0;i < 2 * n;i++){
int t = max(bl[i - 1],rl[i - 1]) + max(br[i],rr[i]);
ans = max(t,ans);
}
printf("%d\n",min(ans,n));
}