程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj(2184)——Cow Exhibition(01背包變形)

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

編輯:關於C++

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

題目的大致意思是:

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


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved