Posted on 2009-03-06 16:45
superman 閱讀(109)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
code 1
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("beads.in", "r", stdin);
8 freopen("beads.out", "w", stdout);
9
10 int n;
11 string s;
12
13 cin >> n;
14 cin >> s;
15
16 for (int i = 0; i < n - 1; i++)
17 s += s[i];
18
19 int rec[1000] = { 0 };
20
21 for (int i = 0; i < 2 * n - 1; i++)
22 {
23 int p = i + 1; char c = s[i];
24 while (true)
25 {
26 if (p == 2 * n - 1)
27 break;
28 if (c == 'w')
29 {
30 if (s[p] != 'w')
31 c = s[p];
32 }
33 else
34 {
35 if (s[p] != c && s[p] != 'w')
36 break;
37 }
38 p++;
39 }
40 rec[i] = p - i;
41 }
42
43 int ans = 0;
44 for (int i = 0; i < 2 * n - 2; i++)
45 ans >?= (rec[i] + rec[i + rec[i]]);
46
47 cout << (ans > n ? n : ans) << endl;
48
49 return 0;
50 }
51
code2
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("beads.in", "r", stdin);
8 freopen("beads.out", "w", stdout);
9
10 int n;
11 string s;
12
13 cin >> n;
14 cin >> s;
15
16 for (int i = 0; i < n - 1; i++)
17 s += s[i];
18
19 int leftRed[1000] = { 0 }, rightRed[1000] = { 0 };
20 int leftBlue[1000] = { 0 }, rightBlue[1000] = { 0 };
21
22 if (s[0] == 'r') leftRed[0] = 1;
23 if (s[0] == 'b') leftBlue[0] = 1;
24 if (s[0] == 'w') leftRed[0] = leftBlue[0] = 1;
25 if (s[2 * n - 2] == 'r') rightRed[2 * n - 2] = 1;
26 if (s[2 * n - 2] == 'b') rightBlue[2 * n - 2] = 1;
27 if (s[2 * n - 2] == 'w') rightRed[2 * n - 2] = rightBlue[2 * n - 2] = 1;
28
29 for (int i = 1; i < 2 * n - 1; i++)
30 {
31 if (s[i] == 'r')
32 {
33 leftRed[i] = leftRed[i - 1] + 1;
34 leftBlue[i] = 0;
35 }
36 if (s[i] == 'b')
37 {
38 leftRed[i] = 0;
39 leftBlue[i] = leftBlue[i - 1] + 1;
40 }
41 if (s[i] == 'w')
42 {
43 leftRed[i] = leftRed[i - 1] + 1;
44 leftBlue[i] = leftBlue[i - 1] + 1;
45 }
46 }
47
48 for (int i = 2 * n - 3; i >= 0; i--)
49 {
50 if (s[i] == 'r')
51 {
52 rightRed[i] = rightRed[i + 1] + 1;
53 rightBlue[i] = 0;
54 }
55 if (s[i] == 'b')
56 {
57 rightRed[i] = 0;
58 rightBlue[i] = rightBlue[i + 1] + 1;
59 }
60 if (s[i] == 'w')
61 {
62 rightRed[i] = rightRed[i + 1] + 1;
63 rightBlue[i] = rightBlue[i + 1] + 1;
64 }
65 }
66
67 int ans = 0;
68 for (int i = 0; i < 2 * n - 2; i++)
69 {
70 int l = max(leftRed[i], leftBlue[i]);
71 int r = max(rightRed[i + 1], rightBlue[i + 1]);
72 ans >?= (l + r);
73 }
74
75 cout << (ans > n ? n : ans) << endl;
76
77 return 0;
78 }
79