题目链接:http://poj.org/problem?id=1661
标准的DP,首先将输入数据按高度进行排序,将开始下落的位置初始化为左右坐标均为x,高度为y的平台(方便统一处理),然后从上至下搜寻最短路径。。
DP的思想已经掌握了,但是各种细节的处理还是远远达不到,这里贴出大神的代码,以示参考
#include<stdio.h> #include<string.h> #include<memory.h> #include<stdlib.h> #define INF 1000000 struct platform{ int lx,rx,h; }p[1010]; int leftmin[1010],rightmin[1010]; int n,MAX; int compare(const void * e1,const void * e2) { struct platform * p1,* p2; p1 = (struct platform *)e1; p2 = (struct platform *)e2; return p2->h - p1->h; } int mintime(int L,int flag) { int y = p[L].h; int x,i,ltime,rtime; if(flag) x = p[L].lx; else x = p[L].rx; for(i=L+1;i<=n;i++) { if(p[i].lx<=x&&p[i].rx>=x) break; } if(i<=n) { if(y - p[i].h > MAX) return INF; } else { if(y > MAX) return INF; else return y; } ltime = y - p[i].h + x - p[i].lx; rtime = y - p[i].h - x + p[i].rx; if(leftmin[i] == -1) leftmin[i] = mintime(i,1); if(rightmin[i] == -1) rightmin[i] = mintime(i,0); ltime += leftmin[i]; rtime += rightmin[i]; if(ltime>rtime) return rtime; else return ltime; } int main(void) { int x,y,i,ncases; scanf("%d",&ncases); while(ncases--) { scanf("%d %d %d %d",&n,&x,&y,&MAX); memset(leftmin,-1,sizeof(leftmin)); memset(rightmin,-1,sizeof(rightmin)); p[0].lx = x; p[0].rx = x; p[0].h = y; for(i=1;i<=n;i++) scanf("%d %d %d",&p[i].lx,&p[i].rx,&p[i].h); qsort(p,n+1,sizeof(struct platform),compare); printf("%d\n",mintime(0,1)); } return 0; }
代码来自于:点击打开链接