思路（存档

原题链接：29349.剑之试炼

‮队团加不）ด้้童帅_者仇复

2024-11-06 20:16:42

发布于：广东

22阅读

0回复

0点赞

建一个状压dp数组，和两个邻接矩阵，一个备用数组（ $32768\times 15,15\times 15$ , $15$ ）.
如果在第一层，就求出11点与其他怪的距离.（矩阵2）
如果不在第一层，将上一层的每个怪到下一层的怪表示出来.（矩阵2）
直接广搜到每个怪，求出最短距离.（矩阵1）
用备用数组计算跨层后（或从11点开始）加上状压dp最后一项的最短时间.
压缩一波，清空dp数组并将 $dp_{1,i}$ 赋值为备用数组的第 $i$ 项.
清空备用数组，状压dp.

如样例#1
第一层：
11建图：（矩阵2）
$\begin{bmatrix} 1\\ 5 \end{bmatrix}$
修改状压dp后的第一项：
$[1,5]$
广搜建图：（矩阵1）
$\begin{bmatrix} 0&4\\ 4&0 \end{bmatrix}$
状压dp最后一项： $[9,5]$

第二层：
建跨层图：（矩阵2）
$[2,4]$
修改状压dp后的第一项：
$[9]$
广搜建图：略
状压dp最后一项： $[9]$

第三层：
建跨层图：（矩阵2）
$\begin{bmatrix} 5\\ 3 \end{bmatrix}$
修改状压dp后的第一项：
$[14,12]$
广搜建图：(矩阵1）
$\begin{bmatrix} 0&6 \\ 6&0\end{bmatrix}$
状压dp最后一项： $[20,18]$

加上打怪的时间后为 $34$ .

有帮助，赞一个

去预览

0/2000

全部评论 3

Macw07
感觉 acgo 是时候可以优化一下讨论了。类似洛谷一样，增加笔记区域，仅自己可见。搜索自己发布的帖子等功能。（相当于是一个小型的博客网站

2024-11-06 来自美国
3
‮队团加不）ด้้童帅_者仇复
顶

2024-11-07 来自广东
0
Macw07
好家伙，acgo 变成了大家的笔记存档地方。

2024-11-06 来自美国
0

全部评论 3

热门讨论