Luogu P2340 [USACO03FALL] Cow Exhibition G （线性DP 01背包转化）

[USACO03FALL] Cow Exhibition G

题目背景

题目描述

奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 $N$ 头奶牛进行了面试，确定了每头奶牛的智商和情商。

贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。

输入格式

第一行：单个整数 $N$，$1\le N\le 400$。

第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数：$S_i$ 和 $F_i$，表示第 $i$ 头奶牛的智商和情商，− $1000\le S_i;F_i\le 1000$。

输出格式

输出单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 $0$。

样例 #1

样例输入 #1

5
-5 7
8 -6
6 -3
2 1
-8 -5

样例输出 #1

8

提示

选择第一头，第三头，第四头奶牛，智商和为−5+6+2 = 3，情商和为7−3+1 = 5。再加

入第二号奶牛可使总和提升到10，不过由于情商和变成负的了，所以是不允许的

---

这道题有两个需要控制的数值，但是我们的dp数组不可能去存两个数值，所以我们可以将其中一个作为一种属性，也就是说我们可以吧牛的智商当做是背包的体积，然后将情商作为存储的数值，这样就将其化为了一个01背包问题。

• 对于这道题的数值范围太大，如果使用二维dp数组会MLE，所以优化为一维，01背包的一维优化方法已经人尽皆知了不再赘述。

---

接下来最重要的一点就是我们的属性可能会出现负数的情况，但是负数是无法作为下标的，那么我们就需要将负数转化为正数。

• 首先我们注意到智商的范围为-1000 ~ 1000，所以其最小的情况就是$-1000$，由于最多可以有400个，那么最坏情况下会达到-400000的级别，那么我们就将所有的下标加上400000就可以了，注意这时候我们的f[i]代表的原本没有被加过的下标为f[j-400000]。

---

并且我们都知道01背包的一维优化需要对体积的搜索顺序进行一些改变，由于智商可能出现负数的情况，我们就需要分开讨论这个问题。

• 在当前枚举到的牛的智商为正数的时候，我们就按照正常的01背包一维优化顺序进行倒序枚举体积。
• 在当前枚举到的牛的智商为负数的时候，这时候我们减去智商就会变大，那么我们就要正着进行枚举体积，与正常情况下相反。

---

• 之后我们还需要注意将dp数组全部初始化为负无穷，并且将dp[0] = 0。

• 最后我们还需要枚举求答案，并且注意答案不能够小于0（因为可以不选）。

CODE:

int s[N];
int b[N];
int f[800005];

void solve(int times)
{
    int n;cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> s[i] >> b[i];
    }
    memset(f,-0x3f,sizeof f);
    f[400000] = 0;
    for(int i = 1;i <= n;i++){
        if(s[i] >= 0){
            for(int j = 800000;j >= s[i];j--){
                f[j] = max(f[j],f[j - s[i]] + b[i]);
            }
        }else{
            for(int j = 0;j <= 800000 + s[i];j++){
                f[j] = max(f[j],f[j - s[i]] + b[i]);
            }
        }
    }

    int res = 0;
    for(int i = 400000;i <= 800000;i++){
        if(f[i] > 0)res = max(res,i + f[i] - 400000);
    }
    cout << res << endl;
}

原文地址：https://blog.csdn.net/2302_79440616/article/details/142304666

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！