USACO Broken Necklace

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
ID: wcr19961
PROG: beads
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
typedef long long LL;
const int maxn = 710;
char s[maxn];
int lr[maxn], lb[maxn], rr[maxn], rb[maxn];
int main() {
freopen("beads.in", "r", stdin);
freopen("beads.out", "w", stdout);
int n;
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; ++i) {
s[n + i] = s[i];
}
int n2 = n << 1;
for (int i = 1; i <= n2; ++i) {
lb[i] = s[i] == 'r' ? 0 : lb[i - 1] + 1;
lr[i] = s[i] == 'b' ? 0 : lr[i - 1] + 1;
}
for (int i = n2; i > 0; --i) {
rb[i] = s[i] == 'r' ? 0 : rb[i + 1] + 1;
rr[i] = s[i] == 'b' ? 0 : rr[i + 1] + 1;
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, max(lb[i - 1], lr[i - 1]) + max(rb[i], rr[i]));
}
printf("%d\n", min(ans, n));
return 0;
}

支付宝扫码领红包