解題區/解題區 - UVa

UVa 13029 - Emoticons

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個由 ^, _ 構成的字串，請湊出最多的 ^_^ 子字串。

Sample Input

1
2
3
4
5
6
5
_^^_^^_
^__^__^
______
^^__^^
^_^^_^

Sample Output

1
2
3
4
5
Case 1: 1
Case 2: 1
Case 3: 0
Case 4: 2
Case 5: 2

Solution

從左掃瞄到右邊，貪心著手容易得到兩種狀態

  • $h1$: ^ 的個數。
  • $h2$: 湊成 ^???_ 的個數，可以從 $h1$ 合併 _ 構成。

然而有一些特殊案例 ^_^_^^，需要重新排列，他們之間有巢狀關係 (^_(^_^)^)，因此建立狀態 $h3$ 為 ^_^???_，若遇到下一個 ^ 貪心拆解成 (^_(^_^)???)。

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
#include <bits/stdc++.h>
using namespace std;
char s[131072];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int n = strlen(s);
        int ret = 0;
        int h1 = 0, h2 = 0, h3 = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '^' && h2) {
                h2--, ret++;
            } else if (s[i] == '^') {
                if (h3 && ret)
                    h2++, h3--;
                else
                    h1++;
            } else if (s[i] == '_' && h1) {
                h1--, h2++;
            } else if (s[i] == '_') {
                if (ret > h3)
                    h3++;
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}