CVBB ACM Team

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. 其他，按照1→2→3的优先级进行排序。