关键词：
题目背景
奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对N 头奶牛进行
了面试，确定了每头奶牛的智商和情商。
题目描述
贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。
输入输出格式
输入格式：
• 第一行：单个整数N，1 ≤ N ≤ 400
• 第二行到第N + 1 行：第i + 1 行有两个整数：Si 和Fi，表示第i 头奶牛的智商和情商，−1000 ≤ Si; Fi ≤ 1000
输出格式：
输出格式
• 单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出0
输入输出样例
说明
选择第一头，第三头，第四头奶牛，智商和为−5+6+2 = 3，情商和为7−3+1 = 5。再加
入第二号奶牛可使总和提升到10，不过由于情商和变成负的了，所以是不允许的
解析：由于这是每个奶牛装或不装，很明显这是一个01背包
状态：dp[i][j]=x表示考虑到1-i头奶牛，智商和为j的最大情商和为x
答案：max｛dp[n][j](0<=j<=400000)｝
转移：dp[i][j]=max(dp[i-1][j-IQ[i]]+EQ[i],dp[i-1][j])
初值：memset(dp,-999999,sizeof(dp))
dp[i][0]=1(0<=i<=n)
但是由于j有可能为负数，所以要将dp数组整体平移
由-400000-400000 变成0-800000
所以代码是这个样子的：
#include<bits/stdc++.h>
using namespace std;
int IQ[401],EQ[401];
int dp[401][800001];
int ans;
int main()
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&IQ[i],&EQ[i]);
memset(dp,-999999,sizeof(dp));
for(int i=0;i<=n;i++) dp[i][400000]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=800000;j++)
if(j>IQ[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-IQ[i]]+EQ[i]);
else
dp[i][j]=dp[i-1][j];
for(int j=1;j<=800000;j++)
dp[i-1][j]=dp[i][j];
for(int i=400000;i<=800000;i++)
if(dp[n][i]>=0) ans=max(ans,dp[n][i]+i-400000);
cout<<ans;
return 0;
但是你只要稍微测试一下就知道，这个代码会MLE。。。
下面来介绍一下我的解决方法：滚动数组！！！
这是指在第i项只与第i-1项有关系的一种dp优化方法，这可以将第i-2项之前省略，能节省空间。
数组滚动后的代码如下：
#include<bits/stdc++.h>
using namespace std;
int IQ[401],EQ[401];
int dp[3][800001];
int ans;
int main()
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&IQ[i],&EQ[i]);
memset(dp,-999999,sizeof(dp));
dp[1][400000]=0;
dp[2][400000]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=800000;j++)
if(j>IQ[i])
dp[2][j]=max(dp[1][j],dp[1][j-IQ[i]]+EQ[i]);
else
dp[2][j]=dp[1][j];
for(int j=1;j<=800000;j++)
dp[1][j]=dp[2][j];
for(int i=400000;i<=800000;i++)
if(dp[1][i]>=0) ans=max(ans,dp[1][i]+i-400000);
cout<<ans;
return 0;
完美解决
洛谷p2340奶牛会展
洛谷P2340奶牛会展用下标表示智商，值表示情商 1#include<bits/stdc++.h>2#defineFor(i,j,k)for(inti=j;i<=k;i++)3usingnamespacestd;45constintN=411;6intn,m;7inta[N],b[N],f[800011];89inlineintread()10{11intx=0,f=1 查看详情
奶牛排队(代码片段)
题意 【问题描述】奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，... 查看详情
奶牛排序——rmq(代码片段)
【问题描述】奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，且中间如果存在... 查看详情
奶牛抗议(代码片段)
题目Description约翰家的N头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i位的奶牛的理智度为Ai，数字 可正可负。约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小... 查看详情
java寻找公牛和奶牛(代码片段)
lougup2344奶牛抗议(代码片段)
题目背景GenericCowProtests,2011Feb题目描述约翰家的N头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i位的奶牛的理智度为Ai，数字可正可负。约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几... 查看详情
p1578奶牛浴场(代码片段)
题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显... 查看详情
usaco2004moofest奶牛集会(代码片段)
题目问题描述约翰的n头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头奶牛的坐标是相... 查看详情
奶牛的聚会(代码片段)
农历新年马上就要到了，奶牛们计划举办一次聚会庆祝新年的到来。但是，奶牛们并不喜欢走太远的路，这会给他们的聚会带来消极情绪，当一头奶牛的消极指数为 w_iwi? ，他参加聚会所需行走的距离为 s_isi? ，那... 查看详情
奶牛家谱cowpedigrees(代码片段)
令人窒息的奶牛题题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3<=N<200)。这些二叉树有如下性质:每一个... 查看详情
[usaco]2004openmoofest奶牛集会(代码片段)
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情
奶牛野炊(代码片段)
Thecowsarehavingapicnic!EachofFarmerJohn‘s K (1≤ K ≤100)cowsisgrazinginoneof N (1≤ N≤1,000)pastures,convenientlynumbered1...N.Thepasturesareconnectedby M 查看详情
洛谷1578：[wc2002]奶牛浴场——题解(代码片段)
...gu.org/problemnew/show/P1578#sub由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置... 查看详情
[luogu2847]奶牛广播-金(代码片段)
...0)为了在他们之间传播信息,想要组织一个"哞哞广播"系统.奶牛们决定去用步话机装备自己而不是在很远的距离之外互相哞哞叫,所以每一头奶牛都必须有一个步话机.这些步话机都有一个限制传播半径,但是奶牛们可以间接地通过中... 查看详情
洛谷p1535游荡的奶牛(代码片段)
P1535游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBessie‘spo 查看详情
排序奶牛的编号(代码片段)
题目描述有N(1≤N≤1000)头奶牛，它们都被标上一个优先等级编号：1，2或3。用来表示它们喝水时的优先次序，编号为l的最优先，编号为2的其次，编号为3的最后。每天奶牛开始时排成一行，但总是很乱，需要你把它们重新排成... 查看详情
poj3263tallestcow(代码片段)
题面FJ的N头奶牛按序号1..N排成一排。每头奶牛都有正整数高度。你只被告知最高的奶牛的高度H（1≤H≤1,000,000）以及该奶牛的位置P.FJ已经列出了“牛17看到牛34”形式的R（0≤R≤10,000）行。这意味着奶牛34至少与奶牛17... 查看详情
观光奶牛(代码片段)
1#include<iostream>2#include<cstdio>3#include<queue>4usingnamespacestd;5typedefdoubledd;6constintmaxn=1007;7constintmaxm=5007;8intn,m,num;9ddl,r,mid;10ddd[maxn];11queue<int>q;1 查看详情