【hihoCoder】1039 : 字符消除

题目：http://hihocoder.com/problemset/problem/1039

给定一个字符串s，只包含'A', 'B', 'C'三种字符

1. 向 s 的任意位置 (包括头和尾) 中插入'A', 'B', 'C'中任意一个字符

2. 递归删除 s 中的相同字符，要求第1步的插入位置使得消除的字符最多

递归删除: "ABCCBCCCAA"->"ABB"->"A'

思路

1. 枚举：向 s 中插入一个字符获得新字符串s', 计算s' 可以删除的字符

2. 递归删除

用stack<Segment>存储每次可以删除的位置。利用先进后出，在删除的时候不用重新计算位置

源码

 1 #include <string>
 2 #include <stack>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 struct Segment
 7 {
 8     Segment(int _s, int _e){ start = _s; end = _e; }
 9     int start;
10     int end;
11 };
12 
13 int remove(string& str)
14 {
15     stack<Segment> segments;
16     int i, j, strLen, score;
17     i = 0, j = 1, score = 0;
18     strLen = str.length();
19     while (j < strLen)
20     {
21         if (str[i] == str[j])
22             ++j;
23         if (j >= strLen || str[i] != str[j])
24         {
25             if (j - i > 1)
26                 segments.push(Segment(i, j));
27             i = j;
28             j = i + 1;
29 
30         }
31         if (j >= strLen)
32         {
33             if (segments.empty())
34                 break;
35             while (!segments.empty())
36             {
37                 Segment tmp = segments.top();
38                 segments.pop();
39                 str.erase(str.begin() + tmp.start, str.begin() + tmp.end);
40                 score = score + tmp.end - tmp.start;
41             }
42             i = 0;
43             j = 1;
44             strLen = str.length();
45         }
46     }
47     return score;
48 }
49 int main()
50 {
51     int cnt, strLen, i, j, score;
52     string str;
53     
54     cin >> cnt;
55     while (cnt-- > 0)
56     {
57         cin >> str;
58         score = 0;
59         strLen = str.length();
60         for (i = 0; i < strLen; i++)
61         {    
62             for (char cha = 'A'; cha <= 'C'; cha++){
63                 string tmp = str;
64                 tmp.insert(i, &cha);
65                 j = remove(tmp);
66                 if (j > score)
67                     score = j;
68             }
69         }
70         cout << score<< endl;
71     }
72     return 0;
73 }

View Code