CVBB ACM Team

2020.07.23 2020-2021 BUAA ICPC Team Supplementary Training 01 (2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest) pro: 7/8/11

2020.07.20 2020牛客暑期多校训练营（第四场） pro: 7/7/10 rk: 3/1111

2020.07.18 2020牛客暑期多校训练营（第三场） pro: 8/12/12 rk: 22/1174 DONE

topcoder dynamic programming 补完 (200 300 400 500 600 700 800)

vp: Codeforces Round #647

【BZOJ2310】ParkII 插头dp 【BZOJ 2960】 跨平面 平面图转对偶图求最小有向图

题源：hdu 6299 http://acm.hdu.edu.cn/showproblem.php?pid=6299

题意：给你n个只有括号的字符串，问你用哪种方法把他们相接之后可以使得构成的完美的括号最长。

观察：假设我们是不断向右拼的，如果“)“过多的话，那么拼接是不合理的(有浪费的)

策略： 考虑贪心，拼接两个串

1. 左括号<右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
2. 左括号>右括号时 尽可能让右括号多的排在前面，若此时右括号相同，再优先将左括号少的排在前面。
3. 左括号=右括号时 将数量多的排在前面。
4. 其他，按照1→2→3的优先级进行排序。