bzoj5441: [Ceoi2018]Cloud computing

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

跟着大佬做题。。

这题也是有够神仙了。观察一下性质，c很小而f是一个限制条件（然而我并不会心态爆炸）

%了一发，就是把电脑和订单一起做背包，订单的c视为负而电脑的v为负，f由大到小排序做背包

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

struct node{int c,f;LL v;}a[];

bool cmp(node n1,node n2){return n1.f==n2.f?n1.c>n2.c:n1.f>n2.f;}

LL f[];

int main()

{

    int n,m;

    scanf("%d",&n);

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

    {

        scanf("%d%d%lld",&a[i].c,&a[i].f,&a[i].v);

        a[i].v=-a[i].v;

    }

    scanf("%d",&m);

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

    {

        scanf("%d%d%lld",&a[i].c,&a[i].f,&a[i].v);

        a[i].c=-a[i].c;

    }

    n+=m;

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

    int maxp=;LL lin;

    memset(f,-,sizeof(f));f[]=;

    lin=f[];

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

    {

        if(a[i].c>)

        {

            for(int j=maxp;j>=;j--)

                if(f[j]!=lin)

                {

                    f[j+a[i].c]=max(f[j+a[i].c],f[j]+a[i].v);

                    if(j+a[i].c>maxp)maxp=j+a[i].c;

                }

        }

        else

        {

            for(int j=-a[i].c;j<=maxp;j++)

                if(f[j]!=lin)

                    f[j+a[i].c]=max(f[j+a[i].c],f[j]+a[i].v);

        }

    }

    LL ans=;

    for(int i=;i<=maxp;i++)ans=max(ans,f[i]);

    printf("%lld\n",ans);

    return ;

}