程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj(1661)——Help Jimmy（二維dp）

poj(1661)——Help Jimmy（二維dp）

編輯：關於C++

題意：

現在共有N個平台，然後一開始它站在坐標為(x,y)的位置，然後它每次下落與往左右走的速度都是1m/s，並且它每次下落的距離不能超過max米。

告訴你每個平台的左右端點的坐標與它的高度，然後問你它到達地面的最早時間是多少。

注：如果Jimmy恰好落在某個平台的邊緣，被視為落在平台上。所有的平台均不重疊或相連。

思路：

這道題一開始卡了我好久。。（我一開始還以為這道題又和Mandown那道題相似，那道題是用線段樹過的。不過我覺得那道題好像也可以用這道題相類似的方法過）

不過這道題狀態方程的定義也讓我更好的增長了思路，

1）首先定義狀態：dp[i][0]：表示從i平台的左邊走到地面的最短時間

dp[i][1]：表示從i平台的右邊走到地面的最短時間

這樣定義子問題就可以往後面推了。

2）狀態轉移：dp[i][0]=h[i]-h[m]+min(dp[m][0]+l[i]-l[m],dp[m][1]+r[m]-l[i]); dp[i][1]=h[i]-h[m]+min(dp[m][1]+r[m]-r[i],dp[m][0]+r[i]-l[m]); //這裡m代表的意義是i平台下面的那個平台

3）卡住我的問題是怎麼找到下面那個平台呢？後來想了想，暴力啊。。。（真是傻了==

我們只需要對所有的台階按高度進行從低到高的排序就好了，然後我們從低到高的依次進行更新就可以了。

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 1111
#define inf 99999999
int dp[maxn][2];
int n,x,y,lmax;
struct node{
	int l,r;
	int h;
}a[maxn];
bool cmp(node a,node b){
	return a.h=0&&a[x].h-a[k].h<=lmax){
		if(k==0){
			dp[x][0]=a[x].h;
		}
		if(k>0&&a[x].l>=a[k].l&&a[x].l<=a[k].r){
			dp[x][0]=a[x].h-a[k].h+min(dp[k][0]+a[x].l-a[k].l,dp[k][1]+a[k].r-a[x].l);
			return ;
		}
		else k--;
	}
	if(a[x].h-a[k].h>lmax) dp[x][0]=inf;
}
void rightime(int x){
	int k=x-1;
	while(k>=0&&a[x].h-a[k].h<=lmax){
		if(k==0){
			dp[x][1]=a[x].h;
		}
		if(k>0&&a[x].r>=a[k].l&&a[x].r<=a[k].r){
			dp[x][1]=a[x].h-a[k].h+min(dp[k][1]+a[k].r-a[x].r,dp[k][0]+a[x].r-a[k].l);
			return ;
		}
		else k--;
	}
	if(a[x].h-a[k].h>lmax) dp[x][1]=inf;
}
int getans(){
	for(int i=1;i<=n+1;i++){
		rightime(i);
		leftime(i);
	}
	return min(dp[n+1][0],dp[n+1][1]);
}
int main(){
	int T;
	scanf(%d,&T);
	while(T--){
		scanf(%d%d%d%d,&n,&x,&y,&lmax);
		for(int i=1;i<=n;i++){
			scanf(%d%d%d,&a[i].l,&a[i].r,&a[i].h);
		}
		a[0].l=x; a[0].r=x; a[0].h=y;
		a[n+1].l=-20000; a[n+1].r=20000; a[n+1].h=0;
		sort(a,a+n+2,cmp);
		int ans=getans();
		printf(%d
,ans);
	}
}