Help Jimmy" 是在下图所示的场景上完成的游戏。
场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。
Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。
设计一个程序，计算Jimmy到底地面时可能的最早时间。
思路：jimmy 从一点开始下落，落到一个平台上时，他可以选择从左边下落，也可以从右边下落，因为可能存在大量重复的情况，用一个数组记录每种计算过的状态。
假如要从可以从一个平台的左边下落到下一个平台，那么a[i].x1>a[i-1].x1&&a[i].x1<=a[i-1].x2, x1,x2分别是平台左右两边的横坐标。
分情况讨论：
1.H[i]-H[m]>ma dp[i][0]=inf,dp[i][1]=inf
2.下面有平台，且H[i]-H[m]<=ma
dp[i][0] = H[i] - H[m] + Min (dp[m][0] + X1[i] - X1[m], dp[m][1] + X2[m] - X1[i]); m为i左边下面的平台的编号
dp[i][1] = H[i] - H[m] + Min (dp[m][0] + X2[i] - X1[m], dp[m][1] + X2[m] - X2[i]); m为i右边下面的平台的编号
下面没有平台 且H[i]-H[m]<=ma
dp[i][0]=H[i],dp[i][1]=H[i]
很容易理解的博客 http://blog.csdn.net/jdplus/article/details/19919531
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> #define maxn 1005 #define inf 0x3f3f3f3f using namespace std; int n,ma,x,y; typedef struct { int x1,x2,h; }P; int cmp(P b,P c) { return b.h<c.h; } P a[maxn]; int dp[maxn][2]; int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&n,&x,&y,&ma); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h); a[n+1].x1=a[n+1].x2=x,a[n+1].h=y; sort(a+1,a+n+2,cmp); for(int i=1;i<=n+1;i++) dp[i][0]=dp[i][1]=inf; for(int i=1;i<=n+1;i++) { int lp,rp; lp=rp=0; for(int j=i-1;j>0;j--) { if(lp==0&&a[i].x1>=a[j].x1&&a[i].x1<=a[j].x2&&a[i].h-a[j].h<=ma) lp=j; if(rp==0&&a[i].x2>=a[j].x1&&a[i].x2<=a[j].x2&&a[i].h-a[j].h<=ma) rp=j; } if(!lp&&a[i].h<=ma) dp[i][0]=a[i].h; if(lp) dp[i][0]=a[i].h-a[lp].h+min(dp[lp][0]+a[i].x1-a[lp].x1,dp[lp][1]+a[lp].x2-a[i].x1); if(!rp&&a[i].h<=ma) dp[i][1]=a[i].h; if(rp) dp[i][1]=a[i].h-a[rp].h+min(dp[rp][0]+a[i].x2-a[rp].x1,dp[rp][1]+a[rp].x2-a[i].x2); } printf("%d ",min(dp[n+1][0],dp[n+1][1])); } return 0; }