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;
}