[bzoj4922]Karp-de-Chant Number

来自FallDream的博客，未经允许，请勿转载，谢谢。

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

普遍认为卡常数是埃及人Qa'a及后人发现的常数。也可认为是卡普雷卡尔(Kaprekar)常数的别称。主要用于求解括号序列问题。

据考证，卡（Qa'a）是古埃及第一王朝的最后一位法老。他发现并研究了一种常数，后世以他的名字叫做卡常数。卡特兰数的起源也是因为卡的后人与特兰克斯结婚，生下来的孩子就叫卡特兰，而他只是发表了祖传的家书而已。Sereja也是卡的后人，提出括号序列问题，也是从家书里得到的资料。然而Sereja为了不让这个秘密公开，于是隐瞒了这道题的真正做法。可是由于卡的后人不是各个都像卡特兰一样爱慕虚荣，这一算法也无法找到。“欲见贤人而不以其道，犹欲其入而闭之门也”。卡之常数的奥秘，需要以一颗诚心去追寻。

现给定n个括号序列，你需要选择若干序列，将它们按一定的顺序从左往右拼接起来，得到一个合法的括号序列。

显然，这个问题可以用卡常数解决，为了检验你是否会卡常数，请写一个程序，计算可以得到的合法的括号序列的长度的最大值。

n<=300

合法的括号序列只要满足前缀和都大等于0并且总和是0就行了。

预处理每个序列的和还有前缀最小值

合法的括号序列可以看成两段接起来，分别由和是正的和和是负的组成。

对于和是正的，按照前缀最小值排序之后背包dp

负的也同理，翻转一下就是同样的做法了。

复杂度n^3

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define MN 300

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

char st[MN+][MN+];

int n,len[MN+],mn[MN+],f[MN*MN+],g[MN*MN+],mx[MN+],top=,top2=,ans=;

struct data{int x,l,len;}q[MN+],q2[MN+];

bool cmp(data x,data y){return x.x>y.x;}

int main()

{

    n=read();

    memset(f,,sizeof(f));

    memset(g,,sizeof(g));

    for(int i=;i<=n;++i)

    {

        scanf("%s",st[i]+);

        for(int j=;st[i][j];++j)

            len[i]+=st[i][j]=='('?:-,

            mn[i]=min(mn[i],len[i]);

        for(int j=strlen(st[i]+),k=;j;--j)

            k+=st[i][j]=='('?:-,mx[i]=max(mx[i],k);

        len[i]>=?(q[++top]=(data){mn[i],len[i],strlen(st[i]+)},):

                  (q2[++top2]=(data){-mx[i],-len[i],strlen(st[i]+)},);

    }

    sort(q+,q+top+,cmp);

    sort(q2+,q2+top2+,cmp);

    f[]=g[]=;

    for(int i=;i<=top;++i)

        for(int j=i*MN;j>=q[i].l-q[i].x;--j)

            f[j]=max(f[j],f[j-q[i].l]+q[i].len);

    for(int i=;i<=top2;++i)

        for(int j=i*MN;j>=q2[i].l-q2[i].x;--j)

            g[j]=max(g[j],g[j-q2[i].l]+q2[i].len);

    for(int i=MN*MN;~i;--i)

        if(f[i]>=&&g[i]>=) ans=max(ans,f[i]+g[i]);

    cout<<ans;

    return ;

}

秒客网

[bzoj4922]Karp-de-Chant Number

相关文章