当前的状态有：传送门的激活状态，已经完成的任务数量，当前的位置（传送门/任务），经过的时间。显然我们会先将所有任务按照 \(t_i\) 升序排序。把前三维列为状态，后一维列为答案，此时我们可以得到一个状态数为 \(O(2^nm^2)\)，转移为 \(O(m)\) 的 dp。
状态数很没救，显然要被优化。但单拉出来哪一维好像都不太能省略。不过分类讨论后我们会发现：
- 若当前位于传送门，由于只要位于传送门就可以传送到任意一个传送门上，所以此时当前的位置是无需被记录的。具体来说，可以设 \(f_{i,S}\) 表示完成 \(i\) 个任务，当前传送门状态为 \(S\)，且正位于传送门上的最小时间。
- 若当前位于某个任务位置上，由于我们指定了某个位置的完成时间，所以此时当前时间是无需被记录的。具体来说，可以设 \(g_{i,S}\) 表示当前位于第 \(i\) 个任务点，传送门状态为 \(S\) 时完成任务的最大数量。
于是我们通过将状态分类讨论，把状态总数缩掉了一维。以 \(S\) 为阶段进行 dp，此时状态数变为了 \(O(2^nm)\)。可以瞎预处理一些东西优化转移复杂度。
总时间复杂度 \(O(2^nm^2)\)，可以通过。
标签：CF1523F,nm,状态,传送门,一维,Favorite,任务,Game,当前 From： https://www.cnblogs.com/ydtz/p/17762696.html