※ 引述《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;
}