洛谷 P2340 Cow Exhibition G 题解

y0k1n0

2025 年 03 月 19 日

45 次浏览

暂无评论

1481字数

动态规划思维

# 洛谷 P2340 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$。

## 解题思路

显然对于每头牛有两种选择， 选或者不选， 因此可以考虑按照背包问题的求解思路求解。可以将智商看作重量， 情商看作价值， 则`dp[i][j]`代表智商为`i`的情况下情商的最大值， 由此即可将原问题转换为01背包问题求解。

由于智商有负数的存在， 而数组的下标不可以为负数， 因此可以考虑数组偏移的方式来计算， 设`offset`为数组偏移的大小， 则原来智商为`i`的位置对应在状态数组中的智商为`i+offset`
此外， 为了优化空间， 可以使用滚动数组`dp[j]`替代原有的二维数组`dp[i][j]`

同时， 由于智商存在负数， 在进行状态更新`dp[j]=max(dp[j], dp[j-s])+f`的时候也要注意更新的顺序。

- 当`s >= 0`时候，第`i`层状态的更新依赖于第`i-1`层中比`j`小的值， 因此应该从大到小遍历
- 当`s < 0`时候， 第`i`层状态的更新依赖于第`i-1`层中比`j`大的值， 因此应该从小到大遍历

## AC代码

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 8e5 + 10;
const int offset = 4e5;
int n, m = 8e5;
int dp[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    memset(dp, -0x3f, sizeof dp);
    dp[0 + offset] = 0;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int s, f;
        cin >> s >> f;
        if(s >= 0)
        {
            for(int j = m; j >= s; j --)
            {
                dp[j] = max(dp[j], dp[j - s] + f);
            }
        }
        else
        {
            for(int j = 0; j - s <= m; j ++)
            {
                dp[j] = max(dp[j], dp[j - s] + f);
            }
        
        }
    }
    int ans = 0;
    for(int i = offset; i <= m; i ++)
    {
        if(dp[i] >= 0)
        {
            ans = max(ans, i - offset + dp[i]);
        }
    }
    cout << ans << endl;
	return 0;
}
```

最后修改：2025 年 03 月 19 日