P2340 [USACO03FALL] Cow Exhibition G
[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;
}