目录题目思路Code题目题目内容某电力公司使用无人机对 n 个电力塔进行巡检。每个电力塔 i 位于坐标 (xi,yi)无人机从基地坐标 (0,0)出发需要依次飞达每个电力塔完成巡检后结束任务无需返回基地。无人机同一时刻只能飞向一个电力塔请规划巡检顺序使无人机飞行的总距离最短两个坐标点间按曼哈顿距离计算即 ∣x1−x2∣∣y1−y2∣输出最短总距离。输入描述第一行输入 n1 n 15。第二行输入 n 个坐标组成的二维数组0 xi,yi 200。输出描述输出最短总距离。样例 1输入3 [[1,2],[3,1],[2,3]]输出8样例 2输入2 [[1,1],[2,2]]输出4思路整体思路用状态压缩动态规划枚举访问集合与当前终点。第一步预处理任意两塔之间的曼哈顿距离。第二步dp[mask][i] 表示访问 mask 且最后位于 i 的最短距离单点状态由基地距离初始化。第三步从每个可达状态向未访问塔转移。边界处理无需返航完整集合下取任意终点的最小值n1 时答案是基地距离。复杂度分析时间 O(2^n*n^2)空间 O(2^n*n)。Codeimport re import sys lines sys.stdin.read().splitlines() n int(lines[0]) # 第一行之后每两个整数按顺序还原为一座塔的坐标。 # coords[i] 保存第 i 座塔的横纵坐标dist[i][j] 保存从塔 i 直接飞到塔 j 的曼哈顿距离。 numbers list(map(int, re.findall(r\d, .join(lines[1:])))) coords [[numbers[2 * i], numbers[2 * i 1]] for i in range(n)] dist [[abs(coords[i][0] - coords[j][0]) abs(coords[i][1] - coords[j][1]) for j in range(n)] for i in range(n)] full (1 n) - 1 infinity 10**9 # dp[mask][last] 表示访问 mask 中全部塔且最后停在 last 的最短距离。 # mask 的二进制第 i 位为 1 表示第 i 座塔已经巡检last 是当前航线最后停留的塔。 dp [[infinity] * n for _ in range(1 n)] for i, (x, y) in enumerate(coords): # 单点状态是基地到第一座塔的曼哈顿距离任务结束无需返航。 # 状态 1i 只访问塔 i所以初始距离就是基地 (0,0) 到该塔的 xy。 dp[1 i][i] x y for mask in range(1 n): for last in range(n): if not mask (1 last) or dp[mask][last] infinity: continue for nxt in range(n): # 掩码已包含的塔不能重复巡检只向未访问塔扩展。 # 加入 nxt 后的新集合是 mask | (1nxt)候选总距离等于当前最短距离加上 last 到 nxt 的距离。 if mask (1 nxt): continue next_mask mask | (1 nxt) candidate dp[mask][last] dist[last][nxt] dp[next_mask][nxt] min(dp[next_mask][nxt], candidate) # 完整集合下可停在任意塔取所有终点状态的最小值。 # 所有塔都访问后可以停在任意塔因此只比较完整掩码这一行不再额外加回基地的距离。 print(min(dp[full]))JSconst fs require(fs); const numbers (fs.readFileSync(0, utf8).match(/\d/g) || []).map(Number); const n numbers[0]; // 首整数是塔数后续每两个整数构成塔坐标。 // coords[i] 保存第 i 座塔的横纵坐标dist[i][j] 保存从塔 i 直接飞到塔 j 的曼哈顿距离。 const coords Array.from({ length: n }, (_, i) [ numbers[1 2 * i], numbers[2 2 * i], ]); const dist Array.from({ length: n }, () Array(n).fill(0)); for (let i 0; i n; i) { for (let j 0; j n; j) { dist[i][j] Math.abs(coords[i][0] - coords[j][0]) Math.abs(coords[i][1] - coords[j][1]); } } const states 1 n, infinity 1e9; // dp[mask][last] 表示访问 mask 后停在 last 的最短距离。 // mask 的二进制第 i 位为 1 表示第 i 座塔已经巡检last 是当前航线最后停留的塔。 const dp Array.from({ length: states }, () Array(n).fill(infinity)); // 状态 1i 只访问塔 i所以初始距离就是基地 (0,0) 到该塔的 xy。 for (let i 0; i n; i) { dp[1 i][i] coords[i][0] coords[i][1]; } for (let mask 0; mask states; mask) { for (let last 0; last n; last) { if (!(mask (1 last)) || dp[mask][last] infinity) { continue; } for (let next 0; next n; next) { // 只向尚未访问的塔扩展保证每座塔恰好一次。 // 加入 next 后的新集合是 mask | (1next)候选总距离等于当前最短距离加上 last 到 next 的距离。 if (mask (1 next)) { continue; } const nextMask mask | (1 next); dp[nextMask][next] Math.min( dp[nextMask][next], dp[mask][last] dist[last][next], ); } } } // 无需返航完整掩码下所有终点取最小值。 // 所有塔都访问后可以停在任意塔因此只比较完整掩码这一行不再额外加回基地的距离。 console.log(Math.min(...dp[states - 1]));【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。