蜗牛——dp三步法

解题思路:

DP三步法

第一步 确认dp元素

a[i]:第i根竿子上的传送门起点

b[i]:第i根竿子上的传送门终点对应a[i-1]

x[i]:第i根竿子到原点的水平距离

第二步 明确状态，得到状态转移方程

蜗牛最终状态为地面状态T(i)

T(i)可以通过T（i-1）+d得到

也可以通过抵达传送终点时间D(i)+往下爬行时间c[i]得到

传送终点可以由同竿子上的一个传送起点爬行抵达，也可以通过T(i-1)+地面爬行抵达d+向上爬行抵达up(i)

D(i)=D(i-1)+min(|b[i]-a[i-1]|,d+up(i))

d=x[i]-x[i-1]*1.0/1.0

由递推关系得到两个状态D(i),T(i)

T(i)=min(T(i-1)+d , D(i)+c(i));

D(i)=min(T(i-1)+|b[i]-a[i-1]| , T[i-1]+d+up(i))

第三步 数据初始化

由于O点无传送门到达1竿只能通过地面爬行

T(0)=d;

D(0)=d+up(0);
参考代码:

import java.io.*;


public class Main {
	public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public static void main(String[] args) throws IOException {
        int n=nextInt();
        int[] x=new int[n];//第i根竹竿距离原点的距离
 
        int[] a =new int[n];//第i根竹竿上传送门的高度
 
        int[] b=new int[n];//从第i个传送门传送到第i+1根竹竿后蜗牛所在的高度
 
        double[] footMin=new double[n];//footMin[i]表示从原点到达第i根竹竿底部的最短时间
 
        double[] doorMin=new double[n];//doorMin[i]表示从原点到达第i根竹竿传送门的最短时间
 
        for (int i=0;i<n;i++)
        {
            x[i]=nextInt();
        }
        for (int i=0;i<n-1;i++){
            a[i]=nextInt();
            b[i]=nextInt();
        }
  footMin[0]=x[0]*1.0;
  doorMin[0]=x[0]*1.0+a[0]*1.0/0.7;
  int d;
  for(int i=1;i<n;i++) {
	  d=x[i]-x[i-1];
	  if(b[i-1]>a[i]) {
		  doorMin[i]=Math.min(doorMin[i-1]+(b[i-1]-a[i])*1.0/1.3,footMin[i-1]+d+a[i]*1.0/0.7);
	  }
	  else {
		  doorMin[i]=Math.min(doorMin[i-1]+(a[i]-b[i-1])*1.0/0.7,footMin[i-1]+d+a[i]*1.0/0.7);
	  }
	  footMin[i]=Math.min(doorMin[i-1]+b[i-1]*1.0/1.3,footMin[i-1]+d*1.0);
  }
    System.out.println(String.format("%.2f",footMin[n-1]));
	}
	private static int nextInt() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
}