BZOJ 4922 Karp-de-Chant Number 贪心+动态规划

Description

卡常数被称为计算机算法竞赛之中最神奇的一类数字，主要特点集中于令人捉摸不透，有时候会让水平很高的选手迷之超时。

普遍认为卡常数是埃及人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

我们可以把所有的括号先处理一边，只留下不匹配的内容。

比如(()))，其实相当于)，

接着我们可以把(看作1，)看作-1，那么根据括号匹配的内容，

我们不停地累计一个值S，要满足:

1.过程中S>=0

2.结果S=0

对于每个处理后的串))...)(...((，

我们得出这个串的值是所有括号的值累加起来，

然后dp[i][j]表示前i个串，这个累计的值为j的最大长度。

转移就是个01背包……

不过要注意，对于当前值j，i这个串能取，前提是这个串的中途S不会小于0

比如说))(，那么前提就是j>=2，要把2个右括号都排除掉。

这个过程可以预处理出来的。

把处理过后的需要左括号的右括号数目看作攻击力，

然后总的左括号减去右括号看作恢复血量，

如何让S>0，这个贪心从bzoj3709里可以得到结论。

代码很丑……

#include<bits/stdc++.h>
using namespace std;
const int 
  N=305,
  M=90005;
int n,f[N][M];
char s[N];
bool flag[N];
struct node{
  int Len,Sum,x,y;
}a[N],ta[N],tb[N];

bool cmp1(node A,node B){return A.x<B.x;}
bool cmp2(node A,node B){return A.y>B.y;}

int Stack[N];
void get(int x){
  int i=1,top=0;
  while (i<=a[x].Len){
    flag[i]=0;
    if (s[i]=='(') flag[i]=1,Stack[++top]=i; else
    if (!top) flag[i]=1;
     else flag[Stack[top--]]=0;
    i++;
  }
  a[x].x=0,a[x].Sum=0;
  for (i=1;i<=a[x].Len;i++)
    if (flag[i])
      if (s[i]=='(') a[x].Sum++; else
        a[x].Sum--,a[x].x=max(a[x].x,-a[x].Sum);
  a[x].y=a[x].x+a[x].Sum;
}
void getorder(){
  int cnt1=0,cnt2=0;
  for (int i=1;i<=n;i++)
    if (a[i].y-a[i].x>0) ta[++cnt1]=a[i];
      else tb[++cnt2]=a[i];
  sort(ta+1,ta+1+cnt1,cmp1);
  sort(tb+1,tb+1+cnt2,cmp2);

  n=0;
  for (int i=1;i<=cnt1;i++) a[++n]=ta[i];
  for (int i=1;i<=cnt2;i++) a[++n]=tb[i];
}
void DP(){
  memset(f,128,sizeof(f));
  f[0][0]=0;int tsum=0;
  for (int i=1;i<=n;i++){
    int now=i&1,pre=now^1;
    for (int j=a[i].x;j<=tsum;j++) f[now][j]=f[pre][j];
    for (int j=a[i].x;j<=tsum;j++)
      if (j+a[i].Sum>=0)
        f[now][j+a[i].Sum]=max(f[now][j+a[i].Sum],f[pre][j]+a[i].Len);
    if (a[i].Sum>0) tsum+=a[i].Sum;
  }
}
int main(){
  scanf("%d",&n);
  for (int i=1;i<=n;i++){
    scanf("%s",s+1);
    a[i].Len=strlen(s+1);
    get(i);
  }
  getorder();

  DP();
  printf("%d\n",f[n&1][0]>0?f[n&1][0]:0);
  return 0;
}