1024问

牛客小白月赛 22 D.收集纸片

Anna ·
更新时间:2024-09-21
· 991 次阅读

题目连接

https://ac.nowcoder.com/acm/contest/4462/D

一开始还想的排序什么鬼，并不是，再一看数据范围，爆搜吧~但是调试了不少时间，码力码力码力！！！

如果可以的话，以后会写一下状态压缩版本，还一点不会。。

更新一下 ，这个代码虽然ac了，我感觉有错误的地方，应该是数据不太行。在这个搜索中我默认拾完最后一个纸片距离最短然后记录最后一个点，再用这个搜到的最短距离+记录的最后一个点和起始点的距离就是答案，明显有问题。

#include #include #include #include #include #include #include #include #include #include #include #include #define IO \ // ios::sync_with_stdio(false); \ // cin.tie(0); \ // cout.tie(0); using namespace std; typedef long long LL; const int maxn = 1e5 + 10; const int inf = 0x3f3f3f3f; struct Node { int x, y; } node[maxn]; int vis[maxn]; int sx, sy; int f; int ans = 0; int t = 0; int T, n, m, k; void dfs(int s, int n) { if (n == 0) { if (t < ans) { f = s; ans = t; return; } return; } for (int i = 1; i > T; while (T--) { cin >> n >> m; cin >> node[0].x >> node[0].y; cin >> k; for (int i = 1; i > node[i].x >> node[i].y; t = 0; ans = inf; memset(vis, 0, sizeof vis); dfs(0, k); // cout << f << endl; ans += abs(node[f].x - node[0].x) + abs(node[f].y - node[0].y); cout << "The shortest path has length " << ans << endl; } return 0; }

正解

#include #include #include #include #include #include #include #include #include #include #include #include #define IO \ // ios::sync_with_stdio(false); \ // cin.tie(0); \ // cout.tie(0); using namespace std; typedef long long LL; const int maxn = 1e5 + 10; const int inf = 0x3f3f3f3f; struct Node { int x, y; } node[maxn]; int vis[maxn]; int sx, sy; int f; int ans = 0; int t = 0; int T, n, m, k; void dfs(int s, int n) { if (n == 0) { t += abs(node[s].x - node[0].x) + abs(node[s].y - node[0].y); if (t < ans) { f = s; ans = t; t -= abs(node[s].x - node[0].x) + abs(node[s].y - node[0].y); return; } t -= abs(node[s].x - node[0].x) + abs(node[s].y - node[0].y); return; } for (int i = 1; i > T; while (T--) { cin >> n >> m; cin >> node[0].x >> node[0].y; cin >> k; for (int i = 1; i > node[i].x >> node[i].y; t = 0; ans = inf; memset(vis, 0, sizeof vis); dfs(0, k); // cout << f << endl; // ans += abs(node[f].x - node[0].x) + abs(node[f].y - node[0].y); cout << "The shortest path has length " << ans << endl; } return 0; }
作者：TTP1128



牛客

1024 个赞
编辑 举报
需要 登录 后方可回复, 如果你还没有账号请 注册新账号
相关文章
三个很特别的CSS小技巧分享
Orianna 2021-07-12
838
【牛客】左右最值最大差
Gelsey 2020-11-09
602
牛客网+华为云+宝塔面板 服务器小白保姆级配置
Elina 2020-07-01
871
【牛客】另类加法
Tama 2020-09-20
557
牛客小白月赛23
Nona 2021-07-24
896
牛客小白月赛23 A-膜法记录（贪心+枚举）
Sahar 2021-06-03
669
牛客 - 奇怪的背包问题增加了(贪心)
Victoria 2021-01-04
790
【牛客】微信红包
Heather 2021-03-08
764
牛客算法周周练1
Haile 2020-10-22
703
牛客练习赛61 - A - 打怪
Gita 2020-01-30
579
牛客网数据库SQL 实战答案解析
Tricia 2021-04-30
712
牛客算法周周练全部题解
Phemia 2020-02-20
788
牛客算法周周练3
Serepta 2020-01-01
819
[ACM]【树形DP】牛客练习赛62 牛牛染颜色
Iona 2020-07-28
600
牛客练习赛62(基于官方题解的补题 A ~ D)
Cerelia 2021-07-02
783
牛客 - 王国(虚树+树的直径)
Kenda 2021-04-05
738
左神算法、牛客网算法-初级2-3（python实现）
Gloria 2020-09-22
987
D 景区路线规划 （期望 DP 牛客算法周周练1）
Talia 2020-04-13
696
【牛客小白月赛23 A】膜法记录 （二进制枚举）
Antonia 2020-11-03
966
牛客练习赛63-B牛牛的鱼缸
Yelena 2021-03-20
752