题解

题目描述

小美在平面上画了 $n$ 个封闭图形，每个图形由若干点描述。激光打印机需要按顺序打印这些图形，打印每个图形时需移动激光发射器到该图形的一个点，并以特定速度绘制。所有图形打印完毕后需返回初始点。求完成所有打印的最短时间。

解题思路

1. 计算周长：每个图形的周长由输入点按顺序连接形成闭合路径的长度决定。
2. 枚举排列顺序：所有可能的图形打印顺序，共 $n!$ 种情况。
3. 动态规划：对每个排列顺序，通过动态规划确定每个图形的最佳起始点，使得移动时间总和最小。
4. 计算总时间：包括各图形的绘制时间、图形间移动时间和返回初始点的时间。

关键点

• 周长计算：按输入点顺序计算闭合路径的总长度。
• 动态规划状态：记录当前处理到第几个图形、当前图形的起始点和初始图形的起始点。
• 时间计算：总时间为绘制时间加上移动时间，其中移动时间通过动态规划优化。

代码实现

C++

#include <bits/stdc++.h>
using namespace std;

// 定义点结构体
struct Point {
    int x, y;
    Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
    // 重载小于运算符，用于排序
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// 定义图形结构体
struct Graph {
    double time;          // 绘制该图形所需时间
    vector<Point> points; // 图形的所有顶点
};

int main() {
    int n, x;
    cin >> n >> x; // 输入图形数量n和移动速度x
    vector<int> y(n); // 存储每个图形的打印速度
    for (int i = 0; i < n; ++i) cin >> y[i];
    
    vector<Graph> graphs(n); // 存储所有图形信息
    
    // 处理每个图形的输入
    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m; // 当前图形的顶点数
        vector<Point> points; // 存储当前图形的顶点
        
        // 输入所有顶点坐标
        for (int j = 0; j < m; ++j) {
            int a, b;
            cin >> a >> b;
            points.emplace_back(a, b);
        }
        
        // 计算图形的周长
        double perimeter = 0.0;
        for (int j = 0; j < m; ++j) {
            const Point& p1 = points[j];
            const Point& p2 = points[(j+1) % m]; // 循环连接首尾
            double dx = p1.x - p2.x;
            double dy = p1.y - p2.y;
            perimeter += sqrt(dx*dx + dy*dy); // 计算两点间距离
        }
        
        // 存储图形信息
        graphs[i].time = perimeter / y[i]; // 绘制时间=周长/打印速度
        graphs[i].points = points;
    }

    vector<int> order(n); // 存储图形处理顺序
    iota(order.begin(), order.end(), 0); // 初始顺序0,1,...,n-1
    double min_total = 1e18; // 初始化最小总时间为极大值
    
    // 枚举所有可能的图形处理顺序
    do {
        // dp_prev记录状态：(当前点,初始点) -> 累计时间
        map<pair<Point, Point>, double> dp_prev;
        
        // 初始化第一个图形的所有可能起点
        const auto& first_graph = graphs[order[0]];
        for (const Point& p : first_graph.points) {
            dp_prev[{p, p}] = 0.0; // 从p点开始，初始移动时间为0
        }
        
        // 处理后续图形
        for (int k = 1; k < n; ++k) {
            const auto& curr_graph = graphs[order[k]];
            map<pair<Point, Point>, double> dp_curr; // 当前状态
            
            // 遍历前一状态
            for (const auto& entry : dp_prev) {
                const Point& prev_p = entry.first.first; // 前一个图形的终点
                const Point& first_p = entry.first.second; // 初始点
                double prev_time = entry.second; // 累计时间
                
                // 尝试当前图形的所有可能起点
                for (const Point& new_p : curr_graph.points) {
                    // 计算移动时间
                    double dx = prev_p.x - new_p.x;
                    double dy = prev_p.y - new_p.y;
                    double dist = sqrt(dx*dx + dy*dy);
                    double move_time = dist / x; // 移动时间=距离/移动速度
                    
                    // 更新状态
                    auto key = make_pair(new_p, first_p);
                    if (!dp_curr.count(key) || prev_time + move_time < dp_curr[key]) {
                        dp_curr[key] = prev_time + move_time;
                    }
                }
            }
            dp_prev = dp_curr;
            if (dp_prev.empty()) break; // 无可行路径则跳过
        }
        
        if (dp_prev.empty()) continue; // 无解情况
        
        // 计算返回初始点的时间
        double min_move = 1e18;
        for (const auto& entry : dp_prev) {
            const Point& last_p = entry.first.first; // 最后一个图形的终点
            const Point& first_p = entry.first.second; // 初始点
            double dx = last_p.x - first_p.x;
            double dy = last_p.y - first_p.y;
            double dist = sqrt(dx*dx + dy*dy);
            double total_move = entry.second + dist / x; // 总移动时间
            if (total_move < min_move) {
                min_move = total_move;
            }
        }
        
        // 计算总时间：移动时间 + 所有图形绘制时间
        double total_time = min_move;
        for (int i : order) {
            total_time += graphs[i].time;
        }
        
        // 更新最小总时间
        if (total_time < min_total) {
            min_total = total_time;
        }
    } while (next_permutation(order.begin(), order.end())); // 尝试所有排列顺序
    
    // 输出结果，保留12位小数
    cout << fixed << setprecision(12) << min_total << endl;
    return 0;
}

Python

import itertools
import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    # 定义哈希函数，用于作为字典键
    def __hash__(self):
        return hash((self.x, self.y))
    
    # 定义相等比较
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    
    # 定义小于比较，用于排序
    def __lt__(self, other):
        if self.x != other.x:
            return self.x < other.x
        return self.y < other.y

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    x = int(input[ptr+1])
    ptr += 2
    y = list(map(int, input[ptr:ptr+n]))
    ptr += n
    graphs = []
    
    # 读取每个图形的数据
    for i in range(n):
        m = int(input[ptr])
        ptr += 1
        points = []
        for j in range(m):
            a = int(input[ptr])
            b = int(input[ptr+1])
            ptr += 2
            points.append(Point(a, b))
        
        # 计算周长
        perimeter = 0.0
        for j in range(m):
            p1 = points[j]
            p2 = points[(j+1)%m]  # 循环连接首尾
            dx = p1.x - p2.x
            dy = p1.y - p2.y
            perimeter += math.hypot(dx, dy)  # 计算两点间距离
        
        # 存储图形信息
        time_i = perimeter / y[i]  # 绘制时间=周长/打印速度
        graphs.append({'time': time_i, 'points': points})
    
    min_total = float('inf')
    
    # 尝试所有可能的图形处理顺序
    for order in itertools.permutations(range(n)):
        first_points = graphs[order[0]]['points']
        dp_prev = {}
        
        # 初始化第一个图形的所有可能起点
        for p in first_points:
            key = (p, p)
            dp_prev[key] = 0.0  # 从p点开始，初始移动时间为0
        
        # 处理后续图形
        for k in range(1, n):
            curr_graph = graphs[order[k]]
            curr_points = curr_graph['points']
            dp_curr = {}
            
            # 遍历前一状态
            for (prev_p, first_p) in dp_prev:
                prev_time = dp_prev[(prev_p, first_p)]
                
                # 尝试当前图形的所有可能起点
                for new_p in curr_points:
                    dx = prev_p.x - new_p.x
                    dy = prev_p.y - new_p.y
                    dist = math.hypot(dx, dy)
                    move_time = dist / x  # 移动时间=距离/移动速度
                    
                    # 更新状态
                    key = (new_p, first_p)
                    total_time = prev_time + move_time
                    if key not in dp_curr or total_time < dp_curr.get(key, float('inf')):
                        dp_curr[key] = total_time
            
            dp_prev = dp_curr
            if not dp_prev:
                break  # 无可行路径则跳过
        
        if not dp_prev:
            continue  # 无解情况
        
        # 计算返回初始点的时间
        min_move = float('inf')
        for (last_p, first_p) in dp_prev:
            dx = last_p.x - first_p.x
            dy = last_p.y - first_p.y
            dist = math.hypot(dx, dy)
            total_move = dp_prev[(last_p, first_p)] + dist / x  # 总移动时间
            if total_move < min_move:
                min_move = total_move
        
        # 计算总时间：移动时间 + 所有图形绘制时间
        total_time = sum(graphs[i]['time'] for i in order) + min_move
        
        # 更新最小总时间
        if total_time < min_total:
            min_total = total_time
    
    # 输出结果，保留12位小数
    print("{0:.12f}".format(min_total))

if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.awt.Point;

class Graph {
    double time;         // 绘制该图形所需时间
    List<Point> points;  // 图形的所有顶点

    Graph(double time, List<Point> points) {
        this.time = time;
        this.points = points;
    }
}

public class Main {
    // 定义状态键类，包含当前点和初始点
    static class Pair {
        Point a;
        Point b;
        Pair(Point a, Point b) {
            this.a = a;
            this.b = b;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return a.equals(pair.a) && b.equals(pair.b);
        }
        @Override
        public int hashCode() {
            return Objects.hash(a, b);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();       // 图形数量
        int x = sc.nextInt();       // 移动速度
        int[] y = new int[n];       // 每个图形的打印速度
        for (int i = 0; i < n; i++) y[i] = sc.nextInt();
        
        List<Graph> graphs = new ArrayList<>(); // 存储所有图形信息
        
        // 读取每个图形的数据
        for (int i = 0; i < n; i++) {
            int m = sc.nextInt();  // 当前图形的顶点数
            List<Point> points = new ArrayList<>();
            for (int j = 0; j < m; j++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                points.add(new Point(a, b));
            }
            
            // 计算周长
            double perimeter = 0.0;
            for (int j = 0; j < m; j++) {
                Point p1 = points.get(j);
                Point p2 = points.get((j + 1) % m); // 循环连接首尾
                double dx = p1.x - p2.x;
                double dy = p1.y - p2.y;
                perimeter += Math.sqrt(dx * dx + dy * dy); // 计算两点间距离
            }
            
            // 存储图形信息
            graphs.add(new Graph(perimeter / y[i], points));
        }
        
        List<Integer> order = new ArrayList<>();
        for (int i = 0; i < n; i++) order.add(i);
        double minTotal = Double.MAX_VALUE;
        
        // 生成所有排列顺序
        do {
            Map<Pair, Double> dpPrev = new HashMap<>();
            List<Point> firstPoints = graphs.get(order.get(0)).points;
            
            // 初始化第一个图形的所有可能起点
            for (Point p : firstPoints) {
                Pair key = new Pair(p, p);
                dpPrev.put(key, 0.0); // 从p点开始，初始移动时间为0
            }
            
            // 处理后续图形
            for (int k = 1; k < n; k++) {
                Graph currGraph = graphs.get(order.get(k));
                List<Point> currPoints = currGraph.points;
                Map<Pair, Double> dpCurr = new HashMap<>();
                
                // 遍历前一状态
                for (Map.Entry<Pair, Double> entry : dpPrev.entrySet()) {
                    Point prevP = entry.getKey().a;   // 前一个图形的终点
                    Point firstP = entry.getKey().b;  // 初始点
                    double prevTime = entry.getValue();
                    
                    // 尝试当前图形的所有可能起点
                    for (Point newP : currPoints) {
                        double dx = prevP.x - newP.x;
                        double dy = prevP.y - newP.y;
                        double dist = Math.sqrt(dx * dx + dy * dy);
                        double moveTime = dist / x; // 移动时间=距离/移动速度
                        
                        // 更新状态
                        Pair key = new Pair(newP, firstP);
                        double totalTime = prevTime + moveTime;
                        if (!dpCurr.containsKey(key) || totalTime < dpCurr.get(key)) {
                            dpCurr.put(key, totalTime);
                        }
                    }
                }
                dpPrev = dpCurr;
                if (dpPrev.isEmpty()) break; // 无可行路径则跳过
            }
            
            if (dpPrev.isEmpty()) continue; // 无解情况
            
            // 计算返回初始点的时间
            double minMove = Double.MAX_VALUE;
            for (Map.Entry<Pair, Double> entry : dpPrev.entrySet()) {
                Point lastP = entry.getKey().a;    // 最后一个图形的终点
                Point firstP = entry.getKey().b;    // 初始点
                double dx = lastP.x - firstP.x;
                double dy = lastP.y - firstP.y;
                double dist = Math.sqrt(dx * dx + dy * dy);
                double totalMove = entry.getValue() + dist / x; // 总移动时间
                if (totalMove < minMove) {
                    minMove = totalMove;
                }
            }
            
            // 计算总时间：移动时间 + 所有图形绘制时间
            double totalTime = minMove;
            for (int i : order) {
                totalTime += graphs.get(i).time;
            }
            
            // 更新最小总时间
            if (totalTime < minTotal) {
                minTotal = totalTime;
            }
        } while (nextPermutation(order)); // 尝试所有排列顺序
        
        // 输出结果，保留12位小数
        System.out.printf("%.12f\n", minTotal);
    }
    
    // 生成下一个排列
    static boolean nextPermutation(List<Integer> a) {
        int i = a.size() - 2;
        while (i >= 0 && a.get(i) >= a.get(i + 1)) i--;
        if (i < 0) return false;
        int j = a.size() - 1;
        while (a.get(j) <= a.get(i)) j--;
        Collections.swap(a, i, j);
        Collections.reverse(a.subList(i + 1, a.size()));
        return true;
    }
}

题目内容

小美在纸上画了 $n$ 个封闭图形，编号为 $1,2,...,n$，第 $i$ 个图形由 $m_i$ 个点描述。他正在捣鼓他的激光打印机打印出这些图形。

这个打印机可以在平面上连续的移动打印，依靠激光发射器实现。激光发射器初始可以位于平面上的任意一个点 $S_0$，随后，由你确定打印顺序，按以下步骤依次打印这 $n$ 个图形：

• 记当前打印的图形编号为 $i$ ；

• 将激光发射器以 $x$ 个单位长度每秒的速度移动到 $m_i$ 点中的其中一个(任选)，作为起始端点 $S_i$

• 将激光发射器以 $y_i$ 个单位长度每秒的速度任意的在纸上移动，直到经过全部 $m_i$ 个点后回到起始端点 $S_i$ ；

• 打印过程中不能暂停；若经过非当前图形的点，忽略不计；

特别的，如果全部图像打印完毕，则将激光发射器以 $x$ 个单位长度每秒的速度移动到把始选择的点 $S_0$ ，完成打印。

直接输出整个打印过程需要的最少时间。特别的，如果图形存在重叠，你需要重复打印重叠的部分。

输入描述

第一行输入两个整数 $n,x(3≦n≦7;1≦x≦1000)$代表图形数量、不打印时激光发射器的移动速度。

第二行输入 $n$ 个整数 $y_1,y_2,...,y_n(1≦y_i≦1000)$ 代表激光发射器打印第 $i$ 个图形的移动速度。

此后，对于第 $i$ 个封闭图形，描述如下：

• 第一行输入一个整数 $m_i(3≦m_i≦7)$ 代表构成该图形的点的数量。

• 此后 $m_i$ 行，每行输入两个整数

$a,b(-1000≦a,b≦1000)$代表点 $(a,b)$。保证同一个图形中没有重复的点。

输出描述

输出一个实数，代表最少时间。由于实数的计算存在误差的量级不超过 $10^{-6}$ 时，您的答案都将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ,当且仅当 $\frac {∣a-b∣}{max(1,∣b∣)}$时，您的答案将被接受。

样例1

输入

3 1
1 2 1
3
-3 3
0 0
-3 -2
3
1 3
3 0
1 -3
4
-2 1
4 3
5 -2
-3 -5

输出

54.507981260725

说明

随后打印图形三

（C$\rightarrow$G$\rightarrow$H$\rightarrow$I$\rightarrow$J$\rightarrow$G）,耗时$\frac{\sqrt40+\sqrt26+\sqrt73+\sqrt37}{1}$ $≈ 26.05034111$。

最后打印图形二

（C$\rightarrow$D$\rightarrow$E$\rightarrow$F$\rightarrow$D$\rightarrow$A）,耗时$\frac{\sqrt6+\sqrt13+\sqrt13}{2}$ $≈ 6.60555128$。

别忘了加上图形于图形间的移动时间，这一部分耗时 $\frac{\sqrt5+\sqrt13+\sqrt10}{1}$ $≈ 9.00389691$