自动搬运

查看原文

来自洛谷，原作者为

	学而思李老师 ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็

搬运于2025-08-24 21:36:33，当前版本为作者最后更新于2020-05-16 10:16:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题是练习01背包变形一道非常好的题

• Q1 为啥要用01背包而不是其它算法？
• 答：我们发现，每只奶牛只有选和不选两种状态，而且是需要决策的，所以01背包绝对是最好的选择

下面将会对 OI 中01背包问题的基本解题步骤进行详细的讲解

一、01背包基本思考步骤

在考场上，思考关于动态规划的问题一般分三步：

1. 确定如何表示状态
2. 推导状态转移方程
3. 思考动规初始状态

下面，我将以此题为例，具体讲解一下这些步骤。

二、如何表示状态

01背包中，一定要想好什么是体积，什么是价值，什么是背包容量。此题中，我们可以把体积看成奶牛的智商，背包容量看成奶牛的个数，价值看成奶牛的情商。所以这题的状态表示就是：

$dp[i][j]$ 表示前 $i$ 只奶牛中，总智商为 $j$ 时情商的最大值

最终的答案是智商与情商之和的最大值，所以可以把 $dp$ 数组扫一遍，取 $dp[n][j]+j$ 的最大值，其中$1\leq j\leq n, dp[n][j] \geq 0$。

一开始想的状态表示可能有错（比如此题），需要在完成后面的步骤后进行修改。

三、状态转移方程

这其实是 dp 里面最难的一步，但此题的状态转移方程还是比较好想的。

每只牛有两种选择：参加会展和不参加会展。我们要求在智商一定的情况下情商的最大值，这其实就是01背包的模板。状态转移方程的推导如下：

• 第 $i$ 只奶牛不参加会展：$dp[i][j]=dp[i-1][j]$
• 第 $i$ 只奶牛参加会展：$dp[i][j]=dp[i-1][j-a[i].iq]+a[i].eq$
• 加上决策，选取上面两种情况的最大值：$dp[i][j]=\max(dp[i-1][j], dp[i-1][j-a[i].iq]+a[i].eq)$

这就是我们此题的状态转移方程了。

当然，此题开二维数组会MLE（拿计算器算一下，学过初赛的应该都会算吧），我们发现每次的 $dp[i][j]$ 只和上一行有关，所以我们可以把 $dp$ 数组优化成一维（这也是01背包模板的一部分）

• Q2：有一些傻傻的奶牛智商居然是负的，这样导致 $j-a[i].iq$ 比 $j$ 大，在 $dp[j]$ 的右上角，而那些聪明的正智商的奶牛会在 $dp[j]$ 的左上角，那压成一维后动规的顺序是什么呢？
• 答：可以在动规的时候判断一下，如果这只奶牛很傻，那么正着dp，否则反着dp。

四、初始状态

最后，我们要考虑dp的初始状态，也就是边界条件。这个过程有点类似于写 dfs 时寻找出口，也就是把一眼能看出答案的地方直接赋值。比如我们这个 $dp[0]$，在没有奶牛时最大情商是多少呢？肯定是 $0$。所以我们的一个边界条件是 $dp[0]=0$

可是，我们的情商能是负数。如果把数组定义成全局变量，默认所有元素为 $0$ 的话，dp的过程中取最大值有可能一直为 $0$。所以，我们还要把数组的其它元素赋值成一个非常小的值。头文件 $\mathtt{cstring}$ 里的 $\mathtt{memset}$ 函数可以解决这个问题，把数组中每一个元素都赋值为 $-\infty$。具体用法： $\mathtt{memset(dp, -0x3f, sizeof\;dp);}$

但是，此时一个棘手的问题出来了：因为 $a[i].iq$ 和 $a[i].eq$ 都有可能是负数，所以会导致数组越界。这时，我们可以把 $dp$ 数组向右移动 $400000$ 位。数组的改变意味着我们状态的定义也会发生改变：

$dp[j]$ 表示在奶牛智商之和为 $j-400000$ 时，情商的最大值。

是不是又学会一招？在数组下标可能为负数时，将其右移可以有效避免数组越界。但是在最后求答案时，不要忘记我们求得其实是 $dp[j]+j-400000$ 的最大值。还有一个易错点：别忘记特判无法保证智商和情商无法保证大于 $0$ 的情况！

最后附核心 dp 代码：

	memset(dp, -0x3f, sizeof dp);
	dp[400000] = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(a[i].iq >= 0)
			for(int j = 800000; j >= a[i].iq; j --)
				dp[j] = max(dp[j], dp[j-a[i].iq] + a[i].eq);
		else
			for(int j = 0; j <= 800000 + a[i].iq; j ++)
				dp[j] = max(dp[j], dp[j-a[i].iq] + a[i].eq);
	}
	for(int i = 400000; i <= 800000; i ++)
		if(dp[i] > 0)
			ans = max(ans, i + dp[i] - 400000);