// 344. 奶牛展览 Cow Exhibition（挑战程序设计竞赛）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include #include #include using namespace std; /* https://www.papamelon.com/problem/344 贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。输入第一行：单个整数 N，1≤N≤100 第二行到第 N+1 行：第i+1 行有两个整数：S_i和 F_i ，表示第 i 奶牛的智商和情商，−1000≤Si,Fi≤1000 输出一个整数：表示情商与智商和的最大值贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 0 样例 1 输入 5 -5 7 8 -6 6 -3 2 1 -8 -5 输出 8 1 -5 7 1 5 -7 1 5 7 2 -5 7 -6 3 2 5 -7 -3 5 2 5 7 3 5 2 5 -7 -3 9 */ const int N = 105; const int M = 1005*N; const int EXTRA = M * 2 + 10; int dp[N][EXTRA]; int n; struct COW { int Eq, Iq; }cows[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> cows[i].Eq >> cows[i].Iq; } for (int i = 0; i < N; i++) { for (int j = 0; j < EXTRA; j++) { dp[i][j] = -99999999; } } dp[0][M] = 0; for (int i = 1; i <= n; i++) { int def = 0; for (int j = 0; j < EXTRA; j++) { dp[i][j] = dp[i - 1][j]; int index = cows[i].Eq; int val = cows[i].Iq; if (j >= index && j - index < EXTRA) { dp[i][j] = max(dp[i][j], dp[i - 1][j - index] + val); } } } int ans = 0; for (int i = M; i < EXTRA; i++) { if (dp[n][i] >= 0) { ans = max(ans, dp[n][i] + i - M); } } cout << ans << endl; return 0; }