题意:给n(n≤103)n(n\leq10^3)n(n≤103)个括号串,求任选若干个以任意顺序组成一个合法括号串的长度最大值。(所有串总长度不超过10410^4104)
解法:考虑先贪心,再背包。
贪心分情况讨论,对整个括号序列有左括号贡献的比较显然,没有任何贡献的在中间随便放,而右括号更多的括号串则是以它右括号比左括号多的数量和上整个括号串所有前缀右括号比左括号大的数量的最大值的和来从小到大排序。
请问如何证明贪心第三种的情况的正确性?