首页 > dd爱探险
开通博客写题解
头像 kilomatutinal
发表于 2026-01-24 11:35:51
（题解建议配合代码一起食用喵~）不会这道题吗？让猫猫来帮帮你吧！这道题可以使用状态压缩动态规划（状压DP）解决喵！我们先看看怎么表示状态的喵~这道题我定义了dp数组dp[i][j][k]喵！i：二进制掩码（其实就是表示状态），表示猫猫已经访问了哪些空间站，比如如i=5（二进制101）代表访问了第0和 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 此在Dasein
发表于 2026-01-24 02:42:42
带权有向完全图的受限哈密顿路径 1. 问题分析 本问题本质上是一个非对称旅行商问题（TSP）的变体。我们需要在包含 个节点的有向完全带权图中，寻找一条能够遍历所有节点的路径（即哈密顿路径），使得总代价最小。 关键约束点分析： 规模约束：。这是一个极其强烈的信号，暗示算法复杂度应为指数级，通常指向 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客937992666号
发表于 2026-01-25 22:56:45
方程的建立：： 表示的状态，即从出发，已经走了所有的点用二进制存储，这个二进制数就是。例如如果，的二进制为，那么从出发经过的所有点有. 表示起点 包括。因为题目说有重力加速与反重力加速，那么可以有四种：从出发，即没有使用重力加速也没有使用反重 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 周康禧
发表于 2026-01-24 15:06:17
因为很小，只有最多16，所以考虑状压dp，代表当前已经访问了mask中二进制已经为1的空间站并且目前在第k个空间站的最小代价，分别代表当前已经访问了mask中二进制已经为1的空间站并且目前在第k个空间站的过程中最大的代价跟最小的代价，因为我们要将一次代价变成，一次代价翻倍，那么就相当于把最大的变成， 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 pandaC222
发表于 2026-01-24 19:36:19
好难 #include<bits/stdc++.h> using namespace std; #define int long long int p[20][20]; int dp[1<<16][16][2][2];//mask,u,g,r const int INF = 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 狂点技能树
发表于 2021-06-01 16:49:08
思路： 类似于 算法竞赛进阶指南 中的例题 最短Hamilton路径 ，只是多了一个”跳跃“的属性 对于原例题，我们采取 状压dp 的思路来求得以每一个状态结束时的最优解 有两维：当前选取值（二进制串）、当前所在位置 对于本题，我们考虑分层图的思路（记录一个类似的状态）也就是记录当前跳跃了几次 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 quchen666
发表于 2026-01-24 15:15:48
#include <bits/stdc++.h> using namespace std; const int N=3e5+10; const int mod = 1e9+7; typedef long long ll; typedef unsigned long long ull; c 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 暮烟十七
发表于 2026-01-24 21:25:57
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 16; int f[1 << N][N][4], a[N][N]; int main() { int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”