Luogu P2340 奶牛会展

Author： YorkWu
发布时间：May 7, 2019
1183 views
No comments
693 words
Categories： OI 题目

*   题意：给定$n$组数，每组数包含2个数字$S\_i$和$F\_i$。 要求：取其中几组数，要求他们的和最大，并且所有$S\_i$的和与$F\_i$的和均大于0。
*   $1\\leq N\\leq 400$ $-1000\\leq S\_i,F\_i\\leq 1000$
*

* * *

*   可以看出，每组数有选与不选两种情况，可以转化为01背包，让$S\_i$作为物品体积，$F\_i$作为物品价值。但是由题意可以发现，$S\_i$有可能为负数，又因为$-1000\\leq S\_i\leq 1000$，所以背包体积可以是$-400000\\leq m\\leq 400000$，因为数组下标不可以为负，所以将整个数组向右平移$400000$个单位，把$400000$当做$0$。
*   这样如果$S_i<0$那么正序枚举，反之倒序枚举。

代码：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    int v[409],w[409];
    int f[800009],n;
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>w[i]>>v[i];
        }
        memset(f,~0x3f,sizeof(f));
        f[400000]=0;
        for(int i=1;i<=n;i++){
            if(v[i]>=0){
                for(int j=800000;j>=v[i];j--){
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
                }
            }
            else{
                for(int j=0;j<=800000+v[i];j++){
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
                }
            }
        }
        int ans=0;
        for(int i=400000;i<=800000;i++) if(f[i]>=0) ans=max(ans,f[i]+i-400000);
        cout<<ans;
        return 0;
    }
```

Last modification：March 14, 2020