poj2184 Cow Exhibition【01背包】+【负数处理】+（求两个变量的和最大）

题目链接：https://vjudge.net/contest/103424#problem/G

题目大意：

给出N头牛，每头牛都有智力值和幽默感，然后，这个题目最奇葩的地方是，它们居然可以是负数！！现在叫你求出其中的牛中，智力值总数和幽默感总数加起来最大的值，当然，智力值的总数必须大于等于零，幽默感总数也是。

解题思路：

转载于>>>大牛博客

对于每头牛，我们有两种选择，要么选，要么不选。看到这，就会觉得跟01背包很像，但是有 2 个变量来描述此状态的特征，智力，幽默感，并且他们可能是负数的。 
如果此题选择dp来解，我们要想办法把它转换成01背包。

下面转换01背包的方法。 
首先，下面的模板是 一维数组解背包问题 。

首先，针对2个变量，智力，幽默感，我们定义i是前i头牛的智力总和，dp[i]存储的是此时智力总和为i时，幽默感总数的最大值。有人或许会问，题目叫我们求智力和幽默感的总数最大值啊，这dp最后得出的只是幽默感总数的最大值啊？没关系，求出整个dp后，将每个d[i] 和 i相加 看谁大就行了，别忘了，i就是智力总和。 

这一步是锁定变量。

开始下一步前，我们先来定义一下dp数组的大小吧。 
最多有100头牛，每个牛的智力范围在 -1000 – 1000 之间， 
那他们的总和就是 落在 -1000*100 – 100*1000这个区间了里，也就是我们的dp要开100*1000*2这么大了。然后模仿坐标系，在100*1000*2这些数里找一个原点，自然的，这个是对称的，很明显远点是100*1000也就是100000了。大于100000的，智力总和大于0，小于100000，智力总和小于0.

当然，这么大的数组我们不可能每个都访问到，这就要做个标记了，既然这里是求最大值，我们就把数组初始化为一个非常小的整数，inf = -100000000.

好了，接下来是关键的负数的处理了。负数的处理很明显和正数不同，但他们都是dp，只不过，处理方式发生了变化。

先是，正数，每头牛有选与不选，仿照01背包

如果知道01背包的优化，上面就很简单了，逆序循环，保证每一个状态都能访问到上一个状态。

s[i] > 0,5-s[i]很明显是小于 5的，此时，dp[5-s[i]]保存的还是上一个状态的值，所以我们可以放心大胆的用。

然后是判断条件,dp[v-s[i]]>inf,记得一开始我们把表示智力值总和的数组的初始化为inf吗？如果，dp[v-s[i]]<=inf,这意味着没有这个智力值没有用到，也就是dp[v] 这个是没有dp[v-s[i]]这个状态，既然没有我们就无视。

来看负数的

仔细看会发现，其实就循环条件不同，为什么这样既可以呢？ 
其实，可以参考01背包的空间优化和完全背包的空间优化。

不管是正数还是负数，我们都推,dp[v]时都要保证，它是由上一个状态的得来的。对于正数而言，上一个状态的智力总和是比当前状态小的。相反，对于负数而言，上一个状态的智力总和是比当前状态大的，s[i] < 0，v-s[i] > v，如果我们还是逆序循环的话，推dp[v]时，比他大的d[v-s[i]]早就改变了，不是上一个状态，那我们的递推就出现问题了，针对这个问题，我们正向循环就可以了。

最后，dp完后

来一个循环

i-100*1000就等于此时的智力值总和了，因为我们让数组发生偏移了。

AC代码如下：

2018-04-30