一不小心拿了运行时间最快qwq（2ms）（截止此时） 要求从一个初始位置开始，经过所有的纸片，最终再回到初始坐标，求走过的最短距离。 方法1：暴力枚举或dfs（2ms） 我们可以用求1~n的全排列，计算所有可能的走法，由于纸片数不超过10，所以走法最多只有10!种。 全排列求法见《算法竞赛进阶指南》
展开全文
这是一个典型的旅行商问题（TSP）变种，需要从起点出发，访问所有目标点（纸片）后返回起点，且只能沿坐标轴方向移动（曼哈顿距离）。由于纸片数量 ，数据规模很小，适合使用状态压缩动态规划（DP + Bitmask）进行精确求解。
核心观察：
两点间最短距离为曼哈顿距离：
访问顺序影响总距离，需要找到最
展开全文
这个题我觉得好难啊，不过A掉的人不少。我的想法就是类似最小生成树的prim算法，不过这里不再是找与已联通的点集相连的最小边，而是找与某点相连的最小边。这样，只需要找n-1次就可以找到一条将所有点连接起来的单向路径，然后按照题意加上终点到起点的距离就可以了。 #include <bits/std
展开全文
A、收集纸片 状态压缩dp ）当初小白赛可以过这道题，是因为前几天做过一题比较类似的小松鼠找松果的题目…… 回到这个题目，题目给出的地图很小最大也就是可以考虑二进制枚举。那么就开一个数组代表以为终点把二进制表示中的1走过一遍的最小花费。那么第一步预处理每两个点之间的距离，以及和源点之间的距离。初始化
展开全文
数据很小，可以考虑直接暴力枚举所有的状态，然后暴力的走
#include <bits/stdc++.h>
#define il inline
using namespace std;
using ll = long long;
using ull = unsigned long lon
展开全文
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(a) a.begin(), a.end()
using vi = vector<int>;
using
展开全文
数据量很小，直接全排列枚举前往点的顺序,再按照path顺序遍历所有点求出答案，时间复杂度为O(n!*n);
#include <bits/stdc++.h>
using namespace std;
int n;
int sx,sy;
int a[11],b[11];
vector<
展开全文
dfs（捡起的纸片数量，当前所在位置）
#include<bits/stdc++.h>
using namespace std;
int n, ans = 1e9;
struct pos
{
int x;
int y;
} paper[20];
bool book[30];
展开全文
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int mp[N][N];
int n;
int minlen=0x3f3f3f3f;
int res;
int x,y;
pair<int,int> p
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
