4922: Karp-de-Chant Number
卡常数被称为计算机算法竞赛之中最神奇的一类数字，主要特点集中于令人捉摸不透，有时候会让水平很高的选手迷之超时。
普遍认为卡常数是埃及人Qa’a及后人发现的常数。也可认为是卡普雷卡尔(Kaprekar)常数的别称。主要用于求解括号序列问题。
据考证，卡（Qa’a）是古埃及第一王朝的最后一位法老。他发现并研究了一种常数，后世以他的名字叫做卡常数。卡特兰数的起源也是因为卡的后人与特兰克斯结婚，生下来的孩子就叫卡特兰，而他只是发表了祖传的家书而已。Sereja也是卡的后人，提出括号序列问题，也是从家书里得到的资料。然而Sereja为了不让这个秘密公开，于是隐瞒了这道题的真正做法。可是由于卡的后人不是各个都像卡特兰一样爱慕虚荣，这一算法也无法找到。“欲见贤人而不以其道，犹欲其入而闭之门也”。卡之常数的奥秘，需要以一颗诚心去追寻。
现给定n个括号序列，你需要选择若干序列，将它们按一定的顺序从左往右拼接起来，得到一个合法的括号序列。
显然，这个问题可以用卡常数解决，为了检验你是否会卡常数，请写一个程序，计算可以得到的合法的括号序列的长度的最大值。
Input
第一行包含一个正整数n(1<=n<=300)，表示括号序列的个数。
接下来n行，每行一个长度在[1,300]之间的括号序列，仅由小括号构成。
Output
输出一行一个整数，即最大长度，注意你可以一个序列也不选，此时长度为0。
Sample Input
3
())
((()
)()
Sample Output
10
HINT
按{2,1,3}的顺序拼接得到((()()))()，总长度为10。
新加两组数据by alone_wolf 2017.6.20
wohenshuai大佬带飞我
思路就是排序后DP
然后数据范围300，所以随便搞
n3也可以过
那么问题就是怎么排序
首先，有用的只有两个值x,y，分别代表，这个字符串的最小值和总和
字符串当然是看作括号序列啦，（为1，）为-1
我们来分类讨论一下:
x>0且y>0 那么这个字符串肯定是分在决策第一类，因为他可以给我们更多的左括号以便后面匹配
x>0且y<0 不存在的，那不成你x>y?
x<0且y>0 这种字符串肯定是分在决策第二类，但若有两个字符串都符合这个规则，则让x大的先决策，正确性显然
x<0且y<0 这种情况就有一点点复杂了
我们考虑现在有两个字符串a和b,现在有的左括号为j
那么我看考虑，若我们同时想拥有a和b(当然，这个单个放是肯定可以的)
先放a，要满足的条件为:j+a.y+b.x>0
先放b，要满足的条件为j+b.y+a.x>0
我们来思考哪一个条件更苛刻，肯定是简单的一个优先
于是就是要比较
a.y+b.x和b.y+a.x
移项就好了
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=305;
const int MAX=1<<30;
int n;
struct qq
{char a[N];int len;int x,y;//最小值 总和
}s[N];
bool cmp (qq a,qq b)//a是否比b优 换句话说是否不需要交换
{if (a.y>=0&&b.y<0) return true;if (b.y>=0&&a.x<0) return false;if (a.y>=0) return a.x>b.x;return a.y-a.x>b.y-b.x;
}
int f[2][100005];
int main()
{scanf("%d",&n);for (int u=1;u<=n;u++){scanf("%s",s[u].a+1);s[u].len=strlen(s[u].a+1);int ooo=0;s[u].x=0;for (int i=1;i<=s[u].len;i++){if (s[u].a[i]=='(') ooo++;else ooo--;s[u].x=min(s[u].x,ooo);}s[u].y=ooo;}for (int u=1;u<=n;u++)for (int i=u+1;i<=n;i++)if (!cmp(s[u],s[i]))swap(s[u],s[i]);/*for (int u=1;u<=n;u++)printf("%d %d %d\n",s[u].x,s[u].y,s[u].len);*/int now=0;for (int u=1;u<=90000;u++) f[0][u]=-MAX;f[0][0]=0;for (int u=1;u<=n;u++){now^=1;for (int i=0;i<=90000;i++)f[now][i]=f[now^1][i];for (int i=0;i<=90000;i++)if (i+s[u].x>=0&&i+s[u].y<=90000)//合法就好 f[now][i+s[u].y]=max(f[now][i+s[u].y],f[now^1][i]+s[u].len);/*for (int i=0;i<=10;i++) printf("%d ",f[now][i]);printf("\n");*/}printf("%d\n",f[now][0]);return 0;
}