题解 P2340 【[USACO03FALL]Cow Exhibition G】
学而思李老师
·
·
题解
此题是练习01背包变形一道非常好的题
- Q1 为啥要用01背包而不是其它算法？
- 答：我们发现，每只奶牛只有选和不选两种状态，而且是需要决策的，所以01背包绝对是最好的选择
下面将会对 OI 中01背包问题的基本解题步骤进行详细的讲解
一、01背包基本思考步骤
在考场上，思考关于动态规划的问题一般分三步：
- 确定如何表示状态
- 推导状态转移方程
- 思考动规初始状态
下面，我将以此题为例，具体讲解一下这些步骤。
二、如何表示状态
01背包中，一定要想好什么是体积，什么是价值，什么是背包容量。此题中，我们可以把体积看成奶牛的智商，背包容量看成奶牛的个数，价值看成奶牛的情商。所以这题的状态表示就是：
最终的答案是智商与情商之和的最大值，所以可以把 $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背包模板的一部分）
dp[j]=\max(dp[j], dp[j-a[i].iq]+a[i].eq)
- 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$ 的最大值。还有一个易错点：别忘记特判无法保证智商和情商无法保证大于 $0$ 的情况！
最后附核心 dp 代码：
```cpp
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);
```