Nescafe 28[图论专题]

Nescafe28模拟赛

T1.升降梯上

题解 :

直接把每层在不同控制槽的情况看成不同的状态然后跑一遍最短路即可

复杂度\(O((nm)log(nm))\)

代码

T2.塔顶试探

题解 :

我们可以把给定的字符串看成一个\(dfs\)序, 然后直接在上面跑区间\(dp\)

\(f_{l,r}\)为字符串上区间\([l,r]\)的所有合法方案, 你每次枚举一个拆分点\(i\),当满足\(s_{l+1}=s_{i-1} \ \ and \ \ s_{i} = s_{r}\)时可以转移 \[ f_{l,r} = f_{l + 1, i - 1} \cdot f_{i,r} \] 可以这么理解一下, 区间\([l+1,i-1]\)可以被看成一个以这个节点的某个儿子节点为子树的情况, \([i,r]\)是这个节点去除那个以那个儿子节点为根的子树的部分, 然后根据乘法原理直接乘起来就好了

我是用记忆化搜索实现的, 常规的区间\(dp\)也可以, 复杂度都是\(O(n^3)\)

代码

T3.礼物运送

Solution1 :

考虑把设状态\(f_{i, S}\)表示从一号节点出发走过的点的集合为\(S\), 最后停留在\(i\)的最小花费

这个可以直接用 $SPFA $ 求出来, 因为这是个点多边少的稀疏图, 并且 $SPFA $ 的常数极小, 所以跑得飞快

\(PS : Dijkstra\)\(T\)两个点

最后直接枚举一下母集跟新一下答案就好了

复杂度\(O(3^n+SPFA)\)

理论上过不了, 单开了\(O2\)后, 最慢的两个点可以极限卡进\(1s\)

Solution2:

延续\(Solution1\)中的想法, 但是上述做法的复杂度不对, 我们考虑重新设计一下状态

\(f_{i,S}\)包含点集S的最优解

我们可以先用 \(Floyd\) 中的题预先处理出多源最短路

然后直接用 $Floyd $ 跑出来的最短路来状压 \(DP\) , 因为这个状态的集合\(S\)并不包括所选的点与点之间路径上的点

有转移方程 : \[ f_{i,S} \to f_{v, S \cup \{v\}} \\ f_{v,S \cup \{v\}} = min\{f_{i,S} + dis_{i,v}\} \]

按照这个状态的含义最后枚举答案的时候, 直接取你枚举的集合的补集就好了

复杂度\(O(n^2\cdot2^n + 2^n)\)

代码

Summary

  • 不要打挂
  • $DP $遇到瓶颈时, 考虑转换一下状态