1111DFS超时考虑使用二分但对于每个答案关键在于如何验证对于每个指定的最大嵌套深度如何求解出是否违背但如果能做到知道是否违背那相当于可以直接知道给定序列里的最小嵌套深度再考虑直接从给定的字符串入手如果拆分后的A是VPS那B是否应当也一定是VPS那或许就是可以枚举A的所有VPS同时记录B的嵌套深度最后取结果这样是暴力遍历要拆解出一个VPS维护一个栈描述A里的左括号那么遇到左括号时可以选择加入A也可以选择加入B遇到右括号选择与A去匹配也可以与B匹配这其中有大量可剪枝的地方即右括号必须始终不能超过左括号的数量那么状态包含A的左括号数量B的左括号数量当前遍历到的位置i以及AB所有的最大嵌套深度嵌套深度取决于曾经的最大左括号数量所以应该是在遇到左括号时尝试去更新最大嵌套深度但还存在一个问题是题目要求给定一个序列而不是最小的嵌套深度数值所以还需要去维护选择吗但这样对于答案的更新会比较困难考虑使用DFS得出的答案再遍历一次字符串来凑出一个可行的答案再遍历原始字符串对于左括号加入A时要求a不能超过res,加入B时要求b也不能这样感觉像是又一次DFS只不过又加了个res的限制条件意外的是超时了贪心如果原序列是合法的那么说明总的左括号数量和总的右括号数量是一致的那么如果A序列如果是合法的那么其左右括号数量一致那么剩下的左右括号数量必然也是一致的即如果A合法那么B也必然合法然后贪心就是说在遇到左括号时尽量放给少的那个序列遇到右括号时尽量去消给左括号多的那个序列可是如何保证按照这样的规则去分配左右括号时最后一定会分出合法的A和B万一最后会剩出多的左括号呢