题目链接：?id=2184
博主也是新学dp的，不保证下面的内容的正确性，可能自己哪里理解错了，欢迎指正。
也是看了其它的解题报告，不过写得有点简略了，理解上花了点时间，下面相当于加深理解。
对于一个新学dp的人来说，这道题是噩梦。负数的处理，状态，状态转移，变量处理。当然，啃掉他，收获绝对很大，对dp会有新的认识。
先来说下题目大意吧，给出N头牛，每头牛都有智力值和幽默感，然后，这个题目最奇葩的地方是，它们居然可以是负数！！现在叫你求出其中的牛中，智力值总数和幽默感总数加起来最大的值，当然，智力值的总数必须大于等于零，幽默感总数也是。
一开始看到我直接跪了，尽管知道这题可以用dp解，但毫无思路，去找解题报告也是看不出个因为所以然。折磨了一两个钟，终于明白了点什么。
暂且不管负数，对于每头牛，我们有两种选择，要么选，要么选。看到这，就会觉得跟01背包很像，但是有 2 个变量来描述此状态的特征，智力，幽默感，并且他们可能是负数的。 如果此题选择dp来解，我们要想办法把它转换成01背包。
下面转换01背包的方法。 首先，下面的模板是 一维数组解背包问题 。
dp[i] = max(dp[i],dp[i-w[i]]+v[i])
首先，针对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，只不过，处理方式发生了变化。
s[i] 第i头牛的智力f[i]第i头牛的幽默感for i ：1 to N //表示第几头牛if(智力是负数）{//处理}else if(智力是正数){//处理}
先是，正数，每头牛有选与不选，仿照01背包
for(int v = 100*1000*2;v>=s[i];v–)if(dp[v-s[i]]>inf)dp[v] = max(dp[v],dp[v-s[i]]+f[i])
如果知道01背包的优化，上面就很简单了，逆序循环，保证每一个状态都能访问到上一个状态。
v = 5;dp [5] = max(dp[5],dp[5-s[i]]+f[i])
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]]这个状态，既然没有我们就无视罗。
来看负数的
for(int v = s[i];v<100*1000*2;v++)if(dp[v-s[i]]>inf)dp[v] = max(dp[v],dp[v-s[i]]+f[i])
仔细看会发现，其实就循环条件不同，，为什么这样既可以呢？ 其实，可以参考01背包的空间优化和完全背包的空间优化。
不管是正数还是负数，我们都推,dp[v]时都要保证，它是由上一个状态的得来的。对于正数而言，上一个状态的智力总和是比当前状态小的。相反，对于负数而言，上一个状态的智力总和是比当前状态大的，s[i] < 0，v-s[i] > v，如果我们还是逆序循环的话，推dp[v]时，比他大的d[v-s[i]]早就改变了，不是上一个状态，那我们的递推就出现问题了，针对这个问题，我们正向循环就可以了。
最后，dp完后
来一个循环
ans = 0;for i:100*1000 to 100*1000*2智力总和要正数嘛if(dp[i]>=0)ans = max(ans,i – 100*1000 + dp[i]);
i-100*1000就等于此时的智力值总和了，因为我们让数组发生偏移了。
01背包的转换，锁定变量，负数处理之开大数组，状态，状态转移，怎样，虽然这题是噩梦，但是做了之后会收获很多技巧。
这是dp解法啦，看讨论区有人暴搜，不知道怎么做到的。
积极的人在每一次忧患中都看到一个机会，
