[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，不过由于情商和变成负的了，所以是不允许的

算法1

(01背包)

首先对于每个牛有参加和不参加两种选择，因此可以初步的判断本题是01背包

1.状态定义

f[i][j] : 表示前i头牛智商总和为j的最大情商值

2.状态计算

(1) 当第i头牛不参加 ： f[i][j] = f[i-1][j];

(2) 当第i头牛参加时：f[i][j] = f[i-1][j-v[i]] + w[i];

(3)总结：f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);

3.初始化

本题是求求解最大价值，并且数据中会有负数存在，初始值为-INF;

memset(f,0x3f,sizeof f);

f[0][0] = 0; //前0头牛，智商为0的最大情商价值为0，因为0头牛吗。。。

4.关键点：

状态转移过程中某个时刻 j 可能为负数，但是下标不能为负，因此统一加上一个很大的数400000；

关于移动400000步：

$400$: 牛的最大数量

$[-1000,1000]$ : 智商/情商的取值范围

$400$ * $[-1000至1000]$ = $[-400000,400000]$ = $[0,800000]$

移动后的400000 对应移动前的0，也就是移动前的最小值

移动后的800000 对应移动前的40000，即移动前的最大值

当前智商为负数时，我们需要正序枚举，这是后减去也不会出现重复情况

当我们已经确定过j = 666666的情况，当j = 666660 时v[i] = - 6; 则j = 666666，重复出现

5.最后答案：

枚举$[400000,800000]$，找最大值

C++ 代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 450;

int n;
int v[N],w[N];
int f[800005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> v[i] >> w[i];
	}
	
	memset(f,-0x3f,sizeof f);   //因为有负数，初始化为最小值
	
	f[400000] = 0;    //f[i] == f[i-400000],即最小值 
	for(int i = 1; i <= n; i++){
		if(v[i] >= 0){   //当前智商是否大于等于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 = -0x3f3f3f3f;

	for(int i = 400000; i <= 800000; i++){
		if(f[i] >= 0) //当且仅当情商大于等于0时，更新答案
		ans = max(ans,i + f[i] - 400000); 
	}
	cout << ans << endl;
	return 0;
}