※ 引述《oin1104 (是oin的说)》之铭言：
: 题目:
: 给你一个字串
: 你可以消除中间的ab得到x分
: 或是消除中间的ba得到y分
: 问你最多能得几分
: 思路:
: 题目的重点就是
: 像是aba
: 如果x>y就要选择ab的组合 得到x分
: 然后消除ab
: 不然就是ba
: 所以需要对两种情况做stack
: 然后要stack两次
: 写成函式之后比较简洁了
想了一下好像不需要真的建一个 stack
先假设 x >= y, 优先消 ab 的结果就会保证 stack 里一定是
bbbaaaaaa
这种形式，所以只要纪录 b 的数量和 a 的数量就好了
来 b 就优先把 a 消掉，没 a 才叠上去
来 a 就先保留
再来就是为什么可以 greedy 取 ab
假如看到一个任意的 'ab'
两个一定至少一个会被消掉，否则最后把这个 ab 消掉就更高分了矛盾
如果不直接消这个 ab，那要嘛 a 和左边的其他 b 消要嘛 b 和右边的其他 a 消
两种都不如直接消 ab，因为留下来的字串相同而消 ab 分数更高
随便写的丑 code, 能过就好
int maximumGain(string s, int x, int y) {
s += 'c';
char a = 'a', b = 'b';
if (x < y) {
swap(a, b);
swap(x, y);
}
// x >= y, choose ab
int b_cnt = 0, a_cnt = 0, ans = 0;
for (char c : s) {
if (c == a) {
a_cnt += 1;
} else if (c == b) {
if (a_cnt) {
ans += x;
a_cnt -= 1;
} else {
b_cnt += 1;
}
} else {
ans += y * min(b_cnt, a_cnt);
a_cnt = 0;
b_cnt = 0;
}
}
return ans;
}