P2340 奶牛会展 DP

\(n\)头牛，每头牛有智商\(s[i]\)情商\(f[i]\)，问如何从中选择几头牛使得智商情商之和最大且情商之和、智商之和非负

\(n\le 400,-10^3\le s[i] \le 10^3\)

看似两维难以处理，我们可以先考虑一维，做体积为智商、价值为情商的01背包，最后遍历体积不为负的状态更新答案即可。

需要注意的是，体积可能为负，所以我们整体加\(400\times1000\)；负数体积遍历背包时，因为已经压缩了一维，原本要倒序遍历体积，但是这里是负数，所以要正序遍历（否则会覆盖之前的状态）

另外这里的背包体积是恰好填满，所以初值要全部设为-INF，而不是\(0\)

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

inline int read(){

    char ch=getchar();int s=0;

    bool isf=0;

    while((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();

    if(ch=='-'){ch=getchar();isf=1;}

    while(ch>='0'&&ch<='9') s=s*10+(ch^'0'), ch=getchar();

    if(isf) return -s;

    return s;

}

#define MAXN 404

#define BASE 400*1000

int n;

int s[MAXN],f[MAXN];

int dp[800008];

int main(){

    n=read();

    int mxs=0;

    for(int i=1;i<=n;++i) s[i]=read(),f[i]=read(),mxs+=s[i];

    memset(dp, -0x3f, sizeof dp);

    dp[BASE]=0;

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

        if(s[i]>=0)

            for(int j=BASE+mxs;j>=s[i];--j)

                dp[j]=max(dp[j], dp[j-s[i]]+f[i]);

        else

            for(int j=s[i];j<=BASE+mxs;++j)

                dp[j]=max(dp[j], dp[j-s[i]]+f[i]);

    }

    int ans=0;

    for(int i=BASE;i<=mxs+BASE;++i)

        if(dp[i]>=0)

            ans=max(ans, i-BASE+dp[i]);

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

    return 0;

}

巴特西

P2340 奶牛会展 DP 背包

P2340 奶牛会展 DP

最新文章

热门文章