superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Section 1.1 - Broken Necklace

Posted on 2009-03-06 16:45 superman 阅读(106) 评论(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 + 1char 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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理