其实我想说这道题我觉得我自己并没有深刻的理解。但是今天做了一下，先把现在的想法记录下来 。

题目的大致意思是：

有N头牛，每头牛都有一个s值代表智商值，f值代表它的幽默值。

然后问你智商值和幽默值的总和值最大是多少，其中必须保证智商值的和与幽默值的和为非负数。

一开始我想到的也是01背包，但是这里还有负值，于是我就没有办法了。于是学习到了一个相当于把坐标平移的方法。

因为这里有-1000到0的值，于是我们把它们全都移到右边去，于是变成了非负值0-2000。

解法：

01背包。

但是要注意的是当x>=0时，我们一维形式的01背包是从后往前查找的（今天我才算真正理解为什么需要的是从前往后推，因为我们要保证前面的不会影响后面的。这句话也许有点抽象，但是我们如果从前面往后面更新的话，那么后面dp得到的值就会发生重复叠加的情况，想想二维的形式也许就可以理解，dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]) ，当前位置的dp是由上一行的dp以及加上自己的那种情况而得出的，所以是倒着查找）

当x<0时，这时我们要正着for，因为x<0时，相当于它是在负轴上的，相当于它不取x（x在这里是负值），那么就变成了dp[i-x]+y，就是相当于去后面的数，也就是为了保证后面对前面不造成影响。其实我个人的想法是把它看成与x轴正方向相对称的，这样就是从前往后查询了。

?

还有对于dp的初始化，这里dp[10000]=0，因为它相当于是坐标原点，要往两边扩展，所以初始化为0.

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; #define maxn 200000 #define inf 99999999 int dp[maxn]; int main(){ int n; scanf(%d,&n); fill(dp,dp+maxn+1,-inf); dp[100000]=0; for(int i=0;i
       
        =0){ for(int j=maxn;j>=x;j--){ dp[j]=max(dp[j],dp[j-x]+y); } } else{ for(int j=0;j<=maxn+x;j++){ dp[j]=max(dp[j],dp[j-x]+y); } } } int res=-inf; for(int i=100000;i<=maxn;i++){ //因为我们要使smart也是非负的，所以要在右半轴上找； if(dp[i]>=0) //dp[i]>=0我们要保证的是fun值也是非负的； res=max(res,dp[i]+i-100000); } if(res<0) printf(0 ); else printf(%d ,res); }
       
      
     
    
   
  

?

?