P2340 [USACO03FALL] Cow Exhibition G
P2340 [USACO03FALL] Cow Exhibition G - 洛谷
题目背景
题目描述
奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 N 头奶牛进行了面试，确定了每头奶牛的智商和情商。
贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。
输入格式
第一行：单个整数 N，1≤N≤400。
第二行到第 N + 1 行：第 i + 1 行有两个整数：Si 和 Fi，表示第 i 头奶牛的智商和情商，−1000≤Si,Fi≤1000。
输出格式
输出单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 0。
输入输出样例
输入 #1
5 -5 7 8 -6 6 -3 2 1 -8 -5输出 #1
8说明/提示
选择第一头，第三头，第四头奶牛，智商和为 −5+6+2=3，情商和为 7−3+1=5。再加入第二号奶牛可使总和提升到 10，不过由于情商和变成负的了，所以是不允许的。
思路：
二维dp
代码：
#include <bits/stdc++.h>
using namespace std;
const int BASE = 400000;//偏移量，将情商和范围 [-400000, 400000] 映射到数组索引 [0, 800000]
const int MAX_J = 800000;// 情商和的最大索引
const int N = 405;
const int INF = 0x8f8f8f8f;// 表示不可达状态的极大负数
int dp[N][MAX_J + 1]; // dp[i][j]: 前i个奶牛选若干头，总情商和为j时的最大智商和
int s[N], f[N];
int main()
{int N;cin >> N;for (int i = 1; i <= N; ++i) {cin >> s[i] >> f[i]; // 读取第i头奶牛的智商和情商}memset(dp, 0x8f, sizeof(dp));//0x8f8f8f8f 是极大负数，0x3f3f3f3f 是极大正数dp[0][BASE] = 0;//枚举前i个奶牛（i从1到N）for (int i = 1; i <= N; ++i) {//枚举所有可能的情商和jfor (int j = 0; j <= MAX_J; ++j) {//不选第i个奶牛，直接继承前i-1个的状态dp[i][j] = dp[i-1][j];//选第i个奶牛 if (j - f[i] >= 0 && j - f[i] <= MAX_J) {if (dp[i-1][j - f[i]] != INF) {dp[i][j] = max(dp[i][j], dp[i-1][j - f[i]] + s[i]);}}}}//遍历情商和非负int max_sum = 0;for (int j = BASE; j <= MAX_J; ++j) {if (dp[N][j] >= 0) { int sum = (j - BASE) + dp[N][j]; // 总情商和 + 总智商和max_sum = max(max_sum, sum);}}cout << max_sum << endl;return 0;
}
思路：
转化为一维的滚动数组
代码：
#include <bits/stdc++.h>
using namespace std;const int BASE = 400000; // 偏移量，处理负数下标
const int MAX_J = 800000; // 情商和的最大索引
const int INF = 0x8f8f8f8f; // 表示不可达的极小值int dp[MAX_J + 1]; // dp[j]: 情商和为j时的最大智商和
int s[405], f[405];int main() {int N;cin >> N;for (int i = 1; i <= N; ++i)cin >> s[i] >> f[i];memset(dp, 0x8f, sizeof(dp)); // 初始化为极小值dp[BASE] = 0; // 初始状态：不选任何奶牛，情商和0，智商和0for (int i = 1; i <= N; ++i) {if (f[i] >= 0) { // 情商非负，逆序避免重复选for (int j = MAX_J; j >= f[i]; --j) {if (dp[j - f[i]] != INF)dp[j] = max(dp[j], dp[j - f[i]] + s[i]);}} else { // 情商为负，正序保证状态正确更新for (int j = 0; j <= MAX_J + f[i]; ++j) {if (dp[j - f[i]] != INF)dp[j] = max(dp[j], dp[j - f[i]] + s[i]);}}}int max_sum = 0;for (int j = BASE; j <= MAX_J; ++j) // 遍历所有非负情商和if (dp[j] >= 0) // 智商和非负max_sum = max(max_sum, (j - BASE) + dp[j]);cout << max_sum << endl;return 0;
}