bzoj 4922: [Lydsy1706月赛]Karp-de-Chant Number 贪心+dp

题意：给定 $n$ 个括号序，让你从中选取一些括号序按照任意顺序拼接，最终生成一个合法的括号序列，求这个合法序列长度最大值.

题解：假设括号序列相对顺序固定，而我们要做的只是判断选还是不选的话可以转化为一个简单的背包问题：

令 $f[i][j]$ 表示考虑前 $i$ 个括号序，左括号比右括号多 $j$ 个的最长长度.

转移为：$f[i][j]=max(f[i][j],f[i-1][j-k]+len[i])$ 其中 $k$ 表示当前序列 $i$ 中右括号比左括号多的个数.

转移的时候让 $j>=0$，这样就不会出现不合法的情况了.

但是，我们要给序列设计一个顺序，这也是本题的难点.

但是，可以看出这个和之前一道贪心题挺像的.

初始血量为 $0$，右括号减血，左括号加血，让你设计一种排序方式使得尽可能拿更多的序列.

那么，显然要将能回血的且右括号更小的放到前面，然后对于不能回血的将左括号多的放前面.

#include <bits/stdc++.h>

#define N 310

using namespace std;

void setIO(string s)

{

    string in=s+".in";

    string out=s+".out";

    freopen(in.c_str(),"r",stdin);

    // freopen(out.c_str(),"w",stdout);

}

struct node

{

    int x,y,z;

    bool operator<(const node a) const

    {

        if(y>0&&a.y<=0) return 1;

        if(y<0&&a.y>=0) return 0;

        if(y>0) return x<a.x;

        return x+y>a.x+a.y;

    }

}a[N];

int f[N][N*N];

char str[N];

int main()

{

    // setIO("input");

    int n,m=0,i,j;

    scanf("%d",&n);

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

    {

        scanf("%s",str);

        a[i].z=strlen(str),m+=a[i].z;

        for(j=0;j<a[i].z;++j)

        {

            a[i].y+=(str[j]=='('?1:-1),a[i].x=max(a[i].x,-a[i].y);

        }

    }

    sort(a+1,a+1+n);

    // for(j=0;j<=m;++j) f[0][j]=-1000000000;

    memset(f[0],0xc0,sizeof(f[0]));

    f[0][0]=0;

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

    {

        for(j=0;j<=m;++j) f[i][j]=f[i-1][j];

        for(j=a[i].x;j<=m;++j)

            if(j+a[i].y>=0&&j+a[i].y<=m)

                f[i][j+a[i].y]=max(f[i][j+a[i].y],f[i-1][j]+a[i].z);

    }

    printf("%d\n",f[n][0]);

    return 0;

}

巴特西

bzoj 4922: [Lydsy1706月赛]Karp-de-Chant Number 贪心+dp

最新文章

热门文章