首页 > 收集纸片
开通博客写题解
头像 RandolphJ
发表于 2020-02-25 13:33:46
一不小心拿了运行时间最快qwq（2ms）（截止此时） 要求从一个初始位置开始，经过所有的纸片，最终再回到初始坐标，求走过的最短距离。 方法1：暴力枚举或dfs（2ms） 我们可以用求1~n的全排列，计算所有可能的走法，由于纸片数不超过10，所以走法最多只有10!种。 全排列求法见《算法竞赛进阶指南》 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 LoGic123456789
发表于 2020-05-19 23:07:11
这个题我觉得好难啊，不过A掉的人不少。我的想法就是类似最小生成树的prim算法，不过这里不再是找与已联通的点集相连的最小边，而是找与某点相连的最小边。这样，只需要找n-1次就可以找到一条将所有点连接起来的单向路径，然后按照题意加上终点到起点的距离就可以了。 #include <bits/std 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 sunrise__sunrise
发表于 2020-05-20 17:55:01
A、收集纸片 状态压缩dp ）当初小白赛可以过这道题，是因为前几天做过一题比较类似的小松鼠找松果的题目…… 回到这个题目，题目给出的地图很小最大也就是可以考虑二进制枚举。那么就开一个数组代表以为终点把二进制表示中的1走过一遍的最小花费。那么第一步预处理每两个点之间的距离，以及和源点之间的距离。初始化 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 19_hanhan
发表于 2020-05-21 13:16:09
题目 题目描述： 我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。 假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。 你只能沿着 x 轴或 y 轴方向移动，从位置 (i,j) 移动到相邻位置 (i+1,j)，(i-1 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 精神病科黄主任
发表于 2020-05-26 11:45:24
因为最多只有10个纸片，所以直接用stl的next_permutation函数暴力枚举全排列。也就是拿纸片的先后顺序，然后每次排列计算求和 更新最小值即可。 #include<bits/stdc++.h> using namespace std; int a[15]; pair<i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”