利用dp解决 help Jimmy

蔚落 2022-01-17 20:07 141阅读 0赞

“Help Jimmy” 是在下图所示的场景上完成的游戏。  
![Help Jimmy][]  
场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。

Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。

设计一个程序，计算Jimmy到底地面时可能的最早时间。  
Input  
第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1\[i\]，X2\[i\]和H\[i\]。H\[i\]表示平台的高度，X1\[i\]和X2\[i\]表示平台左右端点的横坐标。1 <= N <= 1000，-20000 <= X, X1\[i\], X2\[i\] <= 20000，0 < H\[i\] < Y <= 20000（i = 1…N）。所有坐标的单位都是米。

Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。  
Output  
对输入的每组测试数据，输出一个整数，Jimmy到底地面时可能的最早时间。  
Sample Input  
1  
3 8 17 20  
0 10 8  
0 10 13  
4 14 3  
Sample Output  
23

思路:Jimmy从最高的平台往下跳，肯定是一个平台一个平台的跳，那么从原始位置到地面的最短时间=原始位置到下一个平台时间+下一个平台到地面的最短时间。下一个平台有向左向右两种选择，求两者所求得的最短时间即可。

动态规划的应用：用来求解最优化问题。

动态规划的步骤：

1.  确定状态，将问题拆分为形式相同的子问题，使规模减小。
2.  确定动态转移方程，完成递推式
3.  确定边界条件，保证递推的开始

解题准备：用结构体存储平台数据，dp【】【】数组存储每个平台到地面的T,避免重复运算，将平台高度排序（由于平台数据输入时并不是有序的）

解题思路：

1.  将问题拆分为子问题：从x平台到地面时间的最小，则x下方平台到地面的时间也最小。
2.  动态转移方程：从某个平台到地面有两种走法，向左，向右，求最短时间，要取两者最小值。 （1）如果当前平台下有板子：  
    （当前平台为x，下一个平台为m）向左走：  
    ①如果下一平台分别从左右两方向到地面的时间已知,不用再重复计算、  
    dp\[x\]\[0\]=x的高度-m的高度+min(dp\[m\]\[0\],dp\[m\]\[1\]);  
    ②如果未知：dp\[x\]\[0\]=x的高度-m的高度+min（计算m平台从左边到地面的时间，从右边到地面的时间）；  
    （2）当前平台下方无板子，则直接到达地面  
    dp\[x\]\[0\]=x的高度;

\*\*同理可得向右走的条件  
\*\*  
3. 边界条件：到达地面时dp\[x\]\[\]=x的高度

min(dp\[0\]\[0\],dp\[0\]\[1\])即为答案

#include<iostream>
    #include<algorithm> 
    using namespace std;
    int T,N,X,H,MAX;
    struct Node{//每个板子的数据 
    	int x1,x2,h;
    }p[1005];
    int vis[1005][2];//dp记录板子左右端点到地面的时间 vis[n][0]为左端到地面，vis[n][1]为右端到地面 
    int Searchleft(int n);//寻找左下方是否有板子 
    int Searchright(int n);//右下方是否有板子 
    int Lefttime(int n);//从n板子向左出发，到地面的最短时间 
    int Righttime(int n);//从n板右端出发 
    int cmp(Node a,Node b){//对板子排序 
    	return a.h>b.h;
    }
    int main(){
    	cin>>T;
    	while(T--){
    		cin>>N>>X>>H>>MAX;
    		for(int i=1;i<=N;i++){
    			cin>>p[i].x1>>p[i].x2>>p[i].h;
    		}
    		p[0].x1 =X；//把初始位置看成一个点
    		p[0].x2 =X;
    		p[0].h =H;
    		sort(p,p+N+1,cmp);
    		Lefttime(0);//从最原始的板子开始dp 
    		Righttime(0);
    		int ans=min(vis[0][0],vis[0][1]);
    		cout<<ans<<endl;
    	}
    	return 0;
    }
    int Searchleft(int n){
    	for(int i=n+1;i<=N;i++){
    		if(p[i].x2>=p[n].x1&&p[i].x1<=p[n].x1&&abs(p[n].h-p[i].h)<=MAX)
    			return i;
    	}
    	return -1;
    }
    int Searchright(int n){
    	for(int i=n+1;i<=N;i++){
    		if(p[i].x1<=p[n].x2&&p[i].x2>=p[n].x2&&abs(p[n].h-p[i].h)<=MAX)
    			return i;
    	}
    	return -1;
    }
    int Lefttime(int n){
    	int m=Searchleft(n);
    	if(m==-1)//即下方没有板子
    	{
    		if(p[n].h<=MAX)
    			vis[n][0]=p[n].h;
    		else
    			vis[n][0]=99999999; 
    	 } 
    	else
    	{
    		if(vis[m][0]&&vis[m][1]){
    			vis[n][0]=p[n].h -p[m].h+min(vis[m][0]+p[n].x1-p[m].x1,vis[m][1]+p[m].x2-p[n].x1);
    		}
    		else
    		{
    			vis[n][0]=p[n].h -p[m].h+min(Lefttime(m)+p[n].x1-p[m].x1,Righttime(m)+p[m].x2-p[n].x1);
    		}
    	}
    	return vis[n][0];
    }
    int Righttime(int n){
    	int m=Searchright(n);
    	if(m==-1)//没有板子
    	{
    		if(p[n].h<=MAX)
    			vis[n][1]=p[n].h;
    		else
    			vis[n][1]=99999999;
    	 } 
    	else{
    		if(vis[m][0]&&vis[m][1])
    		{
    			vis[n][1]=p[n].h-p[m].h+min(p[n].x2-p[m].x1+vis[m][0],p[m].x2-p[n].x2+vis[m][1]);
    		}
    		else
    		{
    			vis[n][1]=p[n].h-p[m].h+min(p[n].x2-p[m].x1+Lefttime(m),p[m].x2-p[n].x2+Righttime(m));
    		}
    	}
    	return vis[n][1];
    }

[Help Jimmy]: /images/20220118/f613b5d324ca4355bbcb80c996002b25.png