CF1523F

Portal

description

0 时刻你可以选择二维平面上任意一个整点作为起始点。每个单位时间你可以上下左右走或原地不动。平面上有 \(n\) 个处在整点的传送门，你可以走到一个传送门所在的位置并激活它。一旦传送门被激活，你可以在任意时刻立即传送到这个传送门的位置。

现在有 \(m\) 个任务，第 \(i\) 个要求在第 \(t_i\) 个时刻你恰在 \((x_i,y_i)\) 这个位置。

求最多能完成几个任务。

• \(n\leq 14\)

• \(m\leq 100\)

• \(x_i,y_i\leq 10^6\)

• \(t_i\leq 10^9\)

• 输入的都是整数

solution

dp 状态设计很巧妙！

由于 \(n\) 很小，可以把每个传送门是否被激活塞到状态里。

任务要按时间要求依次做，所以把所有任务按照 \(t_i\) 排序。

这样我们可以设计 dp 状态 \(f_{i,msk}\)，表示考虑前 \(i\) 个任务，传送门被激活的状态是 \(msk\) 的最多的能完成的任务个数。

试一试发现这不好转移。

每次转移可以从传送门、任务点到传送门或到任务点。

我们给状态 \(f\) 加上限制，要求完成了第 \(i\) 个任务且在第 \(i\) 个任务点。

这样解决了任务点到任务点的转移。

考虑如何解决剩下的转移。

完成任务要满足时间限制，时间又很大，不能塞到状态里，而转移的时候还要知道之前已经完成了几个任务了，所以可以把已经完成的任务数塞到状态里。

设 \(g_{i,j,msk}\) 表示考虑前 \(i\) 个任务，已经完成了 \(j\) 个，传送门的激活状态是 \(msk\) 且不要求最后处在的位置（事实上，最优的情况下应该在某个传送门或任务点，但是我们可以随时传送，而且这个状态是为了处理传送门到任务点的转移的）的最小时间。

预处理每种传送门激活状态下从任意一个点经传送到达输入的 \(n+m\) 个点的最短距离。

这样就完成了转移。

需要注意这样做是以“目前考虑到前 \(i\) 个任务”为阶段的。

时间复杂度 \(O(2^nnm^2)\)，瓶颈在 \(g\) 的转移上（也就是传送门到传送门），好像不太行，但是可以卡过去。

再仔细考虑一下转移的过程，可以发现我们也可以以 \(msk\) 从小到大为阶段，这样没有必要记录 \(g\) 的第一维了，而且无后效性。这样就做到 \(O(2^nm^2)\) 了

code

Submission #238921553 - Codeforces