题意:
给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;
}