洛谷2340 奶牛会展

题意

有 $N$ 头奶牛，每头奶牛都有智商和情商，要从中选出一些奶牛参会，要求情商总和 和 智商总和 都不能 $< 0$ 。问情商和智商总和最大是多少。

$N\le 400$ ，智商情商 $\le 1000$ 。

题解

可以把智商当作体积，情商当作价值来做背包，最后答案即为 $\max i+f[i]$ 。

因为有负数所以要偏移一下，同时如果当前体积为负数要正序枚举。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,ans,a[405],b[405],f[800005];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        a[i]=read(); b[i]=read();
        if (a[i]<0 && b[i]<0) continue;
        a[++m]=a[i]; b[m]=b[i];
    }
    n=m;
    const int MAX=n*2000,d=n*1000;
    memset(f,~0x3f,sizeof(f));
    f[d]=0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]>=0)
        {
            for (int j=MAX;j>=a[i];j--) f[j]=max(f[j],f[j-a[i]]+b[i]);
        }
        else
        {
            int maxj=MAX+a[i];
            for (int j=0;j<=maxj;j++) f[j]=max(f[j],f[j-a[i]]+b[i]);
        }
    }
    for (int i=d;i<=MAX;i++) if (f[i]>=0) ans=max(ans,i+f[i]);
    return !printf("%d",ans-d);
}