首页 > 代码库 > [bzoj4922]Karp-de-Chant Number

[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 300using namespace std;inline int read(){    int x = 0 , f = 1; char ch = getchar();    while(ch < 0 || ch > 9){ if(ch == -) f = -1;  ch = getchar();}    while(ch >= 0 && ch <= 9){x = x * 10 + ch - 0;ch = getchar();}    return x * f;}char st[MN+5][MN+5];int n,len[MN+5],mn[MN+5],f[MN*MN+5],g[MN*MN+5],mx[MN+5],top=0,top2=0,ans=0;struct data{int x,l,len;}q[MN+5],q2[MN+5];bool cmp(data x,data y){return x.x>y.x;}int main(){    n=read();    memset(f,128,sizeof(f));    memset(g,128,sizeof(g));    for(int i=1;i<=n;++i)     {        scanf("%s",st[i]+1);        for(int j=1;st[i][j];++j)            len[i]+=st[i][j]==(?1:-1,            mn[i]=min(mn[i],len[i]);        for(int j=strlen(st[i]+1),k=0;j;--j)            k+=st[i][j]==(?1:-1,mx[i]=max(mx[i],k);        len[i]>=0?(q[++top]=(data){mn[i],len[i],strlen(st[i]+1)},0):                  (q2[++top2]=(data){-mx[i],-len[i],strlen(st[i]+1)},0);    }    sort(q+1,q+top+1,cmp);    sort(q2+1,q2+top2+1,cmp);    f[0]=g[0]=0;    for(int i=1;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=1;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]>=0&&g[i]>=0) ans=max(ans,f[i]+g[i]);    cout<<ans;    return 0;    }

[bzoj4922]Karp-de-Chant Number