首页 / 算法 / BZOJ4922 Karp-de-Chant Number（贪心+动态规划）

BZOJ4922 Karp-de-Chant Number（贪心+动态规划）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了BZOJ4922 Karp-de-Chant Number（贪心+动态规划），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2252字，纯文字阅读大概需要4分钟。

内容图文

　　首先将每个括号序列转化为三元组(ai,bi,ci)，其中ai为左括号-右括号数量，bi为前缀最小左括号-右括号数，ci为序列长度。问题变为在满足Σai=0，bi+Σaj>=0 (j<i)的情况下，最大化Σci。

　　考虑在确定了选哪些序列的情况下如何排列能够尽量满足条件。显然应该把ai>0的放在前面，<0的放在后面。对于ai>=0，考虑按bi降序排列。因为假设这样排列后第一个不合法的位置是x，要让该位置合法显然应该将x后面的某个三元组i 和前面的交换，但该三元组的bi<bx，且前面位置的Σaj更小，所以交换后仍不合法，所以这样不会更劣。对于ai<0就比较麻烦了，因为发现我们希望尽量按bi升序和按ai降序，但单独按其中一个排都能很容易的找到反例，所以我们按ai-bi降序排列。ai-bi的实际意义相当于后缀最大左括号-右括号数，添加过程中要求左括号数量始终不少于右括号。考虑反过来看，则要求右括号数量始终不少于左括号。由于ai<0，我们发现这个问题和之前的问题是相同的，只是左右括号反了过来，-(ai-bi)就相当于之前的bi。正确性就是这样了。

　　贪心顺序确定后，dp就很显然了，设f[i][j]为前i个括号序列左括号比右括号多j个时的答案即可。

　　果然检验出了我不会卡常数。为什么大家都跑的那么快啊。 

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
usingnamespace std;
#define ll long long
#define N 310
char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)&&(c<‘0‘||c>‘9‘)) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();}
    while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,m,q,f[N][N*N];
char s[N];
struct data{int x,y,z;
}a[N];
bool cmp(const data&a,const data&b)
{
    return a.x>b.x;
}
bool cmp2(const data&a,const data&b)
{
    return a.y>b.y;
}
bool cmp3(const data&a,const data&b)
{
    return a.x-a.y>b.x-b.y;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj4922.in","r",stdin);
    freopen("bzoj4922.out","w",stdout);
    constchar LL[]="%I64d\n";
#elseconstchar LL[]="%lld\n";
#endif
    n=read();
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s+1);a[i].z=strlen(s+1);
        for (int j=1;j<=a[i].z;j++)
        a[i].y=min(a[i].y,a[i].x+=(s[j]==‘(‘?1:-1)),m+=s[j]==‘(‘?1:0;
    }
    sort(a+1,a+n+1,cmp);int x=n+1;
    for (int i=1;i<=n;i++) if (a[i].x<0) {x=i;break;}
    sort(a+1,a+x,cmp2);sort(a+x,a+n+1,cmp3);
    memset(f,200,sizeof(f));f[0][0]=0;
    for (int i=1;i<=n;i++)
        for (int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if (j-a[i].x>=0&&j-a[i].x<=m&&j-a[i].x+a[i].y>=0) f[i][j]=max(f[i-1][j-a[i].x]+a[i].z,f[i][j]);
        }
    cout<<f[n][0];
    return0;
}

 

原文：https://www.cnblogs.com/Gloid/p/10046617.html

内容总结

以上是互联网集市为您收集整理的BZOJ4922 Karp-de-Chant Number（贪心+动态规划）全部内容，希望文章能够帮你解决BZOJ4922 Karp-de-Chant Number（贪心+动态规划）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1295426.html

来源：【匿名】