poj 1661 Help Jimmy

3ヶ月くらいぶりに更新なのでは・・・(困惑)

スペランカー？

1. 概要

ジミーさんが地面まで降りたいので

初期位置(y,x) 落ちることのできる最大の高さ　途中に浮かぶ謎の板の情報

が与えられたとき、ジミーさんが地面にたどり着くまでの最短の時間を求める。

注意したいのが"板の端が同じx座標だった場合は乗れる"ってことだけに注意する。

1. 解法

動的計画法

各板に対して以下のどうなDPテーブルを立てる。

dp[i][j] i番目の板の右端(j=0)と左端(j=1)にたどり着くまでの最短の時間

板を高さ順にソートしておくことで楽に扱えます。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;
typedef pair<int,pair<int,int> > P;
vector<P> ita;

bool c(int i,int j,bool f)
{
	for(int l=i-1;l>j;l--){
		if(f){
			if(ita[j].second.first>=ita[l].second.first && ita[j].second.first<=ita[l].second.second){
				return false;
			}
		}else{
			if(ita[j].second.second>=ita[l].second.first && ita[j].second.second<=ita[l].second.second){
				return false;
			}
		}
	}
	return true;
}

int main()
{
	int z;
	scanf("%d",&z);
	while(z--){
		int n,x,y,h;
		
		int dp[1001][2];
		for(int i=0;i<1001;i++){
			for(int j=0;j<2;j++){
				dp[i][j]=1<<28;
			}
		}
		dp[0][0]=dp[0][1]=0;
		ita.clear();
		scanf("%d%d%d%d",&n,&x,&y,&h);
		ita.push_back(make_pair(y,make_pair(x,x)));

		for(int i=1;i<=n;i++){
			P p;
			scanf("%d%d%d",&p.second.first,&p.second.second,&p.first);
			ita.push_back(p);
		}
		sort(ita.begin(),ita.end(),greater<P>());

		int ans=1<<28;
		for(int i=0;i<=n;i++){
			for(int j=i-1;j>=0;j--){
				if(ita[j].first-ita[i].first<=h && ita[j].first>ita[i].first){
					if(ita[j].second.first>=ita[i].second.first && ita[j].second.first<=ita[i].second.second && c(i,j,true)){
						dp[i][0]=min(dp[i][0],dp[j][0]+(ita[j].first-ita[i].first)+abs(ita[j].second.first-ita[i].second.first));
						dp[i][1]=min(dp[i][1],dp[j][0]+(ita[j].first-ita[i].first)+abs(ita[j].second.first-ita[i].second.second));
					}
					if(ita[j].second.second>=ita[i].second.first && ita[j].second.second<=ita[i].second.second && c(i,j,false)){
						dp[i][0]=min(dp[i][0],dp[j][1]+(ita[j].first-ita[i].first)+abs(ita[j].second.second-ita[i].second.first));
						dp[i][1]=min(dp[i][1],dp[j][1]+(ita[j].first-ita[i].first)+abs(ita[j].second.second-ita[i].second.second));
					}
				}
			}
			if(ita[i].first<=h && c(n+1,i,true)){
				ans=min(ans,dp[i][0]+ita[i].first);
			}
			if(ita[i].first<=h && c(n+1,i,false)){
				ans=min(ans,dp[i][1]+ita[i].first);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

きたねぇとか言うな！！！