poj(2184)——Cow Exhibition（01背包變形）

poj(2184)——Cow Exhibition（01背包變形）

其實我想說這道題我覺得我自己並沒有深刻的理解。但是今天做了一下，先把現在的想法記錄下來 。

題目的大致意思是：

有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);
}