线性DP

import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader stdIn = new BufferedReader(new InputStreamReader(System.in));
    public static PrintWriter stdOut = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static final int N = 2010;
    public static final double INF = Double.MAX_VALUE;
    public static double[][][] f = new double[N][N][2];
    public static double[] aPoint = new double[N];
    public static double[] bPoint = new double[N];
    public static int n, m, d;
    public static double getDist(double x, double y, double a, double b) {
        double res = (x - a) * (x - a) + (y - b) * (y - b);
        return Math.pow(res, 0.5);
    }
    public static void main(String[] args) throws IOException{
        String[] sp = stdIn.readLine().split(" ");
        n = Integer.parseInt(sp[0]); m = Integer.parseInt(sp[1]); d = Integer.parseInt(sp[2]);
        sp = stdIn.readLine().split(" ");
        for(int i = 1; i <= n; i++) aPoint[i] = Double.parseDouble(sp[i-1]);
        sp = stdIn.readLine().split(" ");
        for(int i = 1; i <= m; i++) bPoint[i] = Double.parseDouble(sp[i-1]);
        Arrays.sort(aPoint, 1, n+1); Arrays.sort(bPoint, 1, m+1);
        //初始化状态
        for(int i = 1; i <= n; i++) {
            f[i][0][0] = aPoint[i];
            f[i][0][1] = INF;
        }
        double initB = getDist(0, 0, d, bPoint[1]);
        for(int i = 1; i <= m; i++) {
            f[0][i][1] = initB + bPoint[i] - bPoint[1];
            f[0][i][0] = INF;
        }
        //状态计算
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                f[i][j][0] = Math.min(f[i-1][j][0]+aPoint[i]-aPoint[i-1], f[i-1][j][1]+getDist(d, bPoint[j], 0, aPoint[i]));
                f[i][j][1] = Math.min(f[i][j-1][1]+bPoint[j]-bPoint[j-1], f[i][j-1][0]+getDist(0, aPoint[i], d, bPoint[j]));
            }
        }
        stdOut.println(String.format("%.2f", Math.min(f[n][m][1], f[n][m][0])));
        stdOut.flush();
    }
}

记忆化搜索

import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader stdIn = new BufferedReader(new InputStreamReader(System.in));
    public static PrintWriter stdOut = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static final int N = 2010;
    public static final double INF = Double.MAX_VALUE;
    public static double[] a = new double[N];
    public static double[] b = new double[N];
    public static double[][][] f = new double[N][N][2];
    public static int n, m, d;
    public static double getDist(double a, double b, double x, double y) {
        double res = (a - x)*(a - x) + (b - y)*(b - y);
        return Math.pow(res, 0.5);
    }
    public static double dfs(int i, int j, int k) {
        if((i == n && j == m+1) || (i == n+1 && j == m)) return 0;
        if((i != n && j == m+1) || (i == n+1 && j != m)) return INF;
        if(f[i][j][k] != -1) return f[i][j][k];
        double x = k == 0 ? 0 : d;
        double y = k == 0 ? a[i] : b[j];
        double res1 = dfs(i+1, j, 0);
        if(res1 != INF && i+1 <= n)
            res1 += getDist(0, a[i+1], x, y);
        double res2 = dfs(i, j+1, 1);
        if(res2 != INF && j+1 <= m)
            res2 += getDist(d, b[j+1], x, y);
        f[i][j][k] = Math.min(res1, res2);
        return f[i][j][k];
    }
    public static void main(String[] args) throws IOException{
        String[] sp = stdIn.readLine().split(" ");
        n = Integer.parseInt(sp[0]); m = Integer.parseInt(sp[1]); d = Integer.parseInt(sp[2]);
        sp = stdIn.readLine().split(" ");
        for(int i = 1; i <= n; i++) a[i] = Double.parseDouble(sp[i-1]);
        sp = stdIn.readLine().split(" ");
        for(int i = 1; i <= m; i++) b[i] = Double.parseDouble(sp[i-1]);
        Arrays.sort(a, 1, n+1); Arrays.sort(b, 1, m+1);
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= m; j++) Arrays.fill(f[i][j], -1);
        stdOut.println(String.format("%.2f", dfs(0,0,0)));
        stdOut.flush();
    }
}