1457: 蓝桥杯历届试题-邮局(JAVA题解)

解题思路:记忆化dfs

注意事项:

暴力杯常见的基础搜索题。。一开始在邮局对象内部缓存村民家的位置，被递归内部引用传递绕晕了。。。回头换用一个map数组存储此状态下距离各村民最近的邮局，递归过程中注意状态回溯，本题还可以剪枝来进一步减少时间复杂度。还利用了mem数组存储距离缓存，注意初始化各元素为负数或无穷大。

参考代码:

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

public class Main {
    public static class Person{
        int x, y;
        Person(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static class Station{
        int rank;
        int x, y;
        Station(int x, int y, int rank) {
            this.x = x;
            this.y = y;
            this.rank = rank;
        }
        public double getIns(Person other){
            return Math.sqrt((this.x-other.x) * (this.x-other.x) + (this.y-other.y) * (this.y-other.y));
        }
    }

    static StreamTokenizer cin;
    static PrintWriter out;
    static int n;  // 户数
    static Person[] arr;
    static int m;  // 备选邮局数
    static Station[] stations;
    static int k;  // 要建邮局数
    static double min_value = Integer.MAX_VALUE;
    static int[] targets;
    static double[][] mem;  // 距离缓存
    public static void main(String[] args) throws IOException{
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        n = nextInt();
        m = nextInt();
        k = nextInt();
        arr = new Person[n+1];
        stations = new Station[m+1];
        targets = new int[k];
        for(int i = 1; i < n+1; i++){
            arr[i] = new Person(nextInt(), nextInt());
        }
        for(int i = 1; i < m+1; i++){
            stations[i] = new Station(nextInt(), nextInt(), i);
        }
        mem = new double[n+1][m+1];
        for(int i = 1; i < n+1; i++)
            Arrays.fill(mem[i], -1);
        dfs(0.0, 1, new LinkedList<>(), new int[n+1]);
        TreeSet<Integer> set = new TreeSet<>();
        for(int i = 1;i < n+1; i++)
            set.add(targets[i]);
        for(int target : set)
            out.print(target + " ");
        out.flush();

    }
    static void dfs(double sum, int index, LinkedList<Station> al, int[] map){
        if(al.size() == k){  // 邮局已选择至上限
            if(min_value > sum){
                min_value = sum;
                targets = map;
            }
            return;
        }
        if(index == m+1)  // 已经没有可选的邮局, 表明本次选择失败
            return;
        // 不选index邮局
        int[] newMap = new int[n+1];
        System.arraycopy(map, 1, newMap, 1, n);
        dfs(sum, index+1, al, newMap);
        // 选择index邮局
        // 更新sum
        Station station = stations[index];  // 待选邮局
        if(al.isEmpty()){  // 第一个选择的邮局, 更新一个初始值sum
            for(int i = 1; i < n+1; i++){  // 遍历村民家
                double dis = station.getIns(arr[i]);
                map[i] = index;
                mem[i][index] = dis;
                sum += dis;
            }
        }else{
            for(int j = 1; j < n+1; j++){
                Person p = arr[j];
                double tm = mem[j][map[j]];
                double nm;
                if(mem[j][index] != -1)
                    nm =  mem[j][index];
                else{
                    nm = station.getIns(p);
                    mem[j][index] = nm;
                }
                if(nm < tm) { // 更新
                    sum -= tm;
                    sum += nm;
                    map[j] = station.rank;
                }
            }
        }
        al.add(station);
        newMap = new int[n+1];
        System.arraycopy(map, 1, newMap, 1, n);
        dfs(sum, index+1, al, newMap);
        al.removeLast();  // 状态回退
    }
    static int nextInt() throws IOException{
        cin.nextToken();
        return (int)cin.nval;
    }
}