当前位置: 代码迷 >> 综合 >> poj 1661 Help Jimmy 动态规划
  详细解决方案

poj 1661 Help Jimmy 动态规划

热度:73   发布时间:2024-01-19 05:26:06.0

题意:

给n个用左端点、右端点、高度标识的平台,问一个下落速度,移动速度均为1的点下落到地面的最小时间,其中每次下落距离不能超过输入值MAX.

分析:

动态规划ldp[i]表示从第i块木板左边下落到地面的最小时间,rdp[i]表示从第i块木板右边下落到地面的最小时间。

代码:

//poj 1661
//sep9
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1024;struct Node
{int x,y,h;	
}plat[MAXN];int N,X,Y,MAX;int cmp(Node a,Node b)
{return a.h>b.h;
}
int g[MAXN][3];
int ldp[MAXN];
int rdp[MAXN];
int rRec(int k); int lRec(int k)
{if(ldp[k]!=-1)return ldp[k];if(g[k][0]==-1)if(plat[k].h<=MAX)return ldp[k]=plat[k].h;elsereturn ldp[k]=99999999;int v=g[k][0],p=plat[k].x;ldp[k]=99999999;int d=plat[k].h-plat[v].h;return ldp[k]=min(lRec(v)+p-plat[v].x,rRec(v)+plat[v].y-p)+d; 
}int rRec(int k)
{if(rdp[k]!=-1)return rdp[k];if(g[k][1]==-1)if(plat[k].h<=MAX)return rdp[k]=plat[k].h;elsereturn rdp[k]=99999999;int v=g[k][1],p=plat[k].y;rdp[k]=99999999;int d=plat[k].h-plat[v].h;return rdp[k]=min(lRec(v)+p-plat[v].x,rRec(v)+plat[v].y-p)+d; 
}void solve()
{scanf("%d%d%d%d",&N,&X,&Y,&MAX);plat[0].x=X,plat[0].y=X,plat[0].h=Y;memset(g,-1,sizeof(g));for(int i=1;i<=N;++i)scanf("%d%d%d",&plat[i].x,&plat[i].y,&plat[i].h);					sort(plat,plat+N+1,cmp);for(int i=0;i<=N;++i){for(int j=i+1;j<=N;++j)if(plat[i].h!=plat[j].h&&plat[i].x>=plat[j].x&&plat[i].x<=plat[j].y)if(plat[i].h-plat[j].h<=MAX){g[i][0]=j;break;}for(int j=i+1;j<=N;++j)if(plat[i].h!=plat[j].h&&plat[i].y>=plat[j].x&&plat[i].y<=plat[j].y)if(plat[i].h-plat[j].h<=MAX){g[i][1]=j;break;}}int s;for(s=0;s<=N;++s)if(plat[s].x==X&&plat[s].y==X&&plat[s].h==Y)break;memset(ldp,-1,sizeof(ldp));memset(rdp,-1,sizeof(rdp));printf("%d\n",lRec(s));	
//	for(int i=0;i<=N;++i){
//		puts(""); 
//		printf("id:%d x,y,h:%d %d %d\n",i,plat[i].x,plat[i].y,plat[i].h);
//		printf("have next %d %d\n",g[i][0],g[i][1]);
//		printf("ans %d %d",ldp[i],rdp[i]);
//		puts(" ");
//	}}int main()
{int cases;scanf("%d",&cases);while(cases--){solve();}return 0;	
} 


  相关解决方案