CF1523F Favorite Game
给定 \(n\) 个传送门和 \(m\) 个地点。传送门需要提前前往才能打开,你可以不用任何时间传送到任何一个传送门,你可以步行 \(1\) 个单位 \(1\) 秒。每个任务要求你在第 \(t_i\) 秒在某个地点,求能完成任务的数目最大值。你可以从任意地点开始。
\(0\leq n\leq14\) , \(1\leq m\leq100\) , \(1\leq x_i,y_i\leq10^6\) , \(1\leq t_i\leq 10^9\) 。
首先肯定是状压传送门的状态,于是有一个朴素的暴力 \(f[i][j][k]\) 表示现在打开的门状态为 \(i\) ,在地点 \(j\) ,完成了 \(k\) 个任务的最短用时。这样的话转移需要向打开下一个传送门或前往下一个任务地点转移,复杂度 \(O(2^n\times(n+m)^2\times n)\) ,不可过。
考虑到当人在任务地点时,时间一定是 \(t_i\) ,在传送门时,具体在哪一个点不重要。因此考虑分开计算这 \(2\) 种情况,各可以省下 \(1\) 维状态。
设 \(f[i][j]\) 表示传送门集合为 \(i\) ,完成 \(j\) 个任务,现在在传送门的最短时间
\(g[i][j]\) 表示传送门集合为 \(i\) ,现在在 \(j\) 点的最大完成任务(此时时间为 \(t_j\) )。
那么还需要预处理出所有传送门集合到某个点的距离。
这样预处理复杂度 \(O(2^n\times n\times(n+m))\) ,转移复杂度也是 \(O(2^n\times n\times(n+m))\) (从 \(4\) 个方面转移:现在在传送门/任务点,接下来去打开传送门/另一个任务点)。可过。
标签:CF1523F,传送门,地点,Favorite,任务,times,leq,Game From: https://www.cnblogs.com/zhouzizhe/p/16815664.html