【C++贪心分治】1717. 删除子字符串的最大得分|1867

本文涉及知识点

贪心分治

LeetCode1717. 删除子字符串的最大得分

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。
删除子字符串 “ab” 并得到 x 分。
比方说，从 “cabxbae” 删除 ab ，得到 “cxbae” 。
删除子字符串"ba" 并得到 y 分。
比方说，从 “cabxbae” 删除 ba ，得到 “cabxe” 。
请返回对 s 字符串执行上面操作若干次能得到的最大得分。
示例 1：
输入：s = “cdbcbbaaabab”, x = 4, y = 5
输出：19
解释：

删除 “cdbcbbaaabab” 中加粗的 “ba” ，得到 s = “cdbcbbaaab” ，加 5 分。
删除 “cdbcbbaaab” 中加粗的 “ab” ，得到 s = “cdbcbbaa” ，加 4 分。
删除 “cdbcbbaa” 中加粗的 “ba” ，得到 s = “cdbcba” ，加 5 分。
删除 “cdbcba” 中加粗的 “ba” ，得到 s = “cdbc” ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。
示例 2：
输入：s = “aabbaaxybbaabb”, x = 5, y = 4
输出：20
提示：
1 <= s.length <= 10⁵
1 <= x, y <= 10⁴
s 只包含小写英文字母。

本文涉及知识点

贪心分治

简化情况

s只包括ab,x >= y。
性质一：n1 = min(a的数量,b的数量)，无论如何操作一定能且只能删除n1次。无论那种操作都会让a和b的数量减1，故n1次后没有a或没有b。以任意方式操作n2次后,n2< n1，一定能继续操作。选择任何一个连续a，那的左右边界不会都是空，和还有b矛盾。
推论一：根据性质一，任意操作n1次后，一定剩余n - n1 $\times$ 2 个a或b。
由于x>=y，求最多能消除多少次ab，令为n3次，则可以消除n1-n3次ba。
如果s[i]前面有没有消除的a，则消除ba。如果没有，则此b无法消除扔掉。
令s[i2]是b，是s[i1]是a，消除不劣于不消除。下面分四种情况证明：
如果最优解两者都没消除，消除更优。
如果s[1]被s[i3]消除，i2<i3， s[i4]和s[i2]消除，两者交换也是最优解。
如果s[1]被s[i3]消除，i2<i3， s[i2]没消除，换成s[i2]消除s[i1]，效果一样。
s[i4]和s[i2]消除，s[i1]没消除。，换成s[i2]消除s[i1]，效果一样。

分治

如果x < y， x和y互换，s中的a和b互换。
如果s[i]不是a或b，则拆分成s[0…i-1]和s[i+1,n-1]不影响结果。同理将非ab将s拆分若干个只有只包括ab的子串。
拆分规则：初始start =-1 。如果start是-1，如果s[i]是ab，则start=i；如果start不是-1，如果s[i]不是ab，则Do(start,i)。start=-1。注意：为了不处理边界情况，在s的末尾增加’z’ 。
时间复杂度：O(n)

代码

核心代码

class Solution {public:int maximumGain(string s, int x, int y) {s += 'z';if (x < y) {swap(x, y);for (auto& ch : s) {if ('a' == ch) {ch = 'b';}else if ('b' == ch) {ch = 'a';}}}auto Do = [&](int left, int r) {int ca = 0,cab=0,cb=0;for (; left < r; left++) {if ('b' == s[left]) {if (ca > cab) {cab++;}cb++;}else {ca++;}}return x * cab + y * (min(ca, cb) - cab);};int start = -1;		int ret = 0;for (int i = 0; i < s.length(); i++) {bool b = ('a' == s[i]) || ('b' == s[i]);if (-1 == start) {if (b) { start = i; }}else {if (!b) {ret += Do(start, i);start = -1;}}}return ret;}};

单元测试

string s;int x, y;TEST_METHOD(TestMethod11){s = "cdbcbbaaabab", x = 4, y = 5;auto res = Solution().maximumGain(s, x, y);AssertEx(19, res);}TEST_METHOD(TestMethod12){s = "aabbaaxybbaabb", x = 5, y = 4;auto res = Solution().maximumGain(s, x, y);AssertEx(20, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功