程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu(3016) Man Down(線段樹查詢更新+dp）

hdu(3016) Man Down(線段樹查詢更新+dp）

編輯：C++入門知識

hdu(3016) Man Down(線段樹查詢更新+dp）

這道題目可以說是游戲的簡化版。

題目的大致意思是：

首先我們只有兩種板，一種使能量增加，另一種卻使能量減少。

最開始人物站在最高層，然後它一開始有100的生命值，它每次下落只能掉到離他最近的木板上去，當然他只能從左端點或者是右端點往下掉。

但是如果沒有板滿足如下情況的話，那麼他就掉到最底下去了，如果此時他的能量小於等於0的話，那麼他就會死亡，那麼則輸出-1；否則輸出他所能獲得能量的最大值。

現在的任務是叫你輸出最大所能獲得最大能量值。

思路：

1）我們要找到當前區間的分別從左右端點下去離他最近的下面那個區間

在這裡可以用線段樹進行維護，但是這東西還是很巧妙啊，真是難想。。。

我們這裡找到的某個板的左右端點的a[i].left或是a[i].right是指它下落會落到的那塊板的標號。

線段樹中query操作這裡其實與染色操作相類似的，就是查找到已經被染色的區間的標號。

update操作其實就是對從l，r區間進行染色，染為第i的顏色。

2）找到所能獲得的最大能量值，這裡要dp來做，雖然我沒有想到這道題竟然可以這樣轉化方程：

dp方程：dp[left]=max(dp[left],dp[i]+a[a[i].left].val) , dp[left]等於要不是不經過第i塊木板而下來的，要不是經過第i塊木板下來的，這樣的話就要加上第i塊木板所含有的價值，顯然，dp方程就是在這兩個方案中尋找最大的價值。

#include
#include
#include
#include
#include
using namespace std;
#define maxn 111111
int dp[maxn];
struct node{
	int l,r;
	int color;
}tree[maxn*4];
struct hh{
	int xl,xr;
	int h,val;
	int left,right;
}a[maxn];
bool cmp(hh a,hh b){
	return a.h>1;
	int temp=v<<1;
	build(l,mid,temp);
	build(mid+1,r,temp+1);
}www.Bkjia.com
void update(int l,int r,int v,int cnt){
	if(l<=tree[v].l&&tree[v].r<=r){
		tree[v].color=cnt;
		return; 
	}
	if(tree[v].color!=-1) pushdown(v);
	int temp=v<<1;
	int mid=(tree[v].l+tree[v].r)>>1;
	if(r<=mid) update(l,r,temp,cnt);
	else if(l>mid) update(l,r,temp+1,cnt);
	else{
		update(l,mid,temp,cnt);
		update(mid+1,r,temp+1,cnt);
	}
}
int query(int t,int v,int l,int r){
	if(tree[v].color!=-1){
		return tree[v].color;
	}
	int mid=(tree[v].l+tree[v].r)>>1;
	int temp=v<<1;
	if(t<=mid) query(t,temp,l,mid);
	else if(t>mid) query(t,temp+1,mid+1,r);
}
int main(){
	int n;
	while(~scanf(%d,&n)){
		memset(dp,0,sizeof(dp));
		int lmax=-1;
		for(int i=1;i<=n;i++){
			scanf(%d%d%d%d,&a[i].h,&a[i].xl,&a[i].xr,&a[i].val);
			if(lmax=1;i--){
			if(dp[i]>0){
				dp[a[i].left]=max(dp[a[i].left],dp[i]+a[a[i].left].val);
				dp[a[i].right]=max(dp[a[i].right],dp[i]+a[a[i].right].val);
			}
		}
		if(dp[0]<=0) printf(-1
);
		else printf(%d
,dp[0]);
	}
}