调皮人生

文章
5
资源
0
加入时间
3年0月9天

【AtCoder】E - Magical Ornament 图论 状压dp

题意:告诉你有哪些两两可以相邻,问你能不能排列出一个包含一串数的序列,且序列长度最小。思路:不知道是不是想复杂了。写完感觉不是这个位置的题该有的难度(应该是我太菜了)。1.首先,建图,相邻的对就连边,把题意转化成在该图上跑出一个最短路径包含序列中的所有点(点可重复)。2.因为走的点的先后顺序未知,所以我们只能通过bfs得到单次从s开始到各点的最短路径,下一步要考虑顺序问题。3.用dp[i][j]dp[i][j]dp[i][j]表示,走完i所表示的集合中的点,且最后一步是走到第j个点时的最优解。其