SP703 SERVICE - Mobile Service 题目分析
前言
目前这道题是最基础的，四倍经验里面的 \(T_2\) 与此一样，\(T_3\) 有点卡空间，但是还好，方案用 short 或者 char 即可优化，\(T_4\) 一样，有些卡常，问题不大。
分析题目性质
没有什么十分有用的性质。
思路
注意到：分配干活的只有 \(3\) 个人。
看到这么小的数很容易想到三维或者四维 \(dp\) 或者是 状态压缩 \(dp\)，很显然是前者。
设 \(f_{i,a_1,a_2,a_3}\) 表示第 \(i\) 个请求后，三个人的位置分别为 \(a_1,a_2,a_3\) 的最小成本。
转移是简单的，不过多赘述。
时间复杂度 \(\mathcal{O}(nL^3).\)
考虑优化状态。
首先 \(i\) 只是跟上一维有关，所以直接把它删掉。
即 \(f_{a_1,a_2,a_3}\) 表示当前三个人的位置分别为 \(a_1,a_2,a_3\) 的最小成本。
我们发现当前的转移必定会有一个人到达 \(p_i\)，也就是说，我们只需要保留另外两个人的状态（不能等于 \(p_{i-1}\)）即可，而第三个人表示的就是上一次做任务的人（即现在在 \(p_{i-1}\) 的人）。
综上，我们可以设 \(f_{a_1,a_2}\) 表示上一次没有做任务经过这次任务之后的两个人的位置在 \(a_1,a_2\) 的最小成本。
不难的转移：
\[f_{a_1,a_2}=\min\{f_{a_1,a_2}+C_{p_{i-1},p_i},f_{a_1,p_{i-1}}+C_{a_2,p_i},f_{p_{i-1},a_2}+C_{a_1,p_i}\} \]时间复杂度 \(\mathcal{O}(nL^2).\)
初始化：显然地 \(f_{1,2}=f_{1,3}=f_{2,1}=\dots=f_{3,1}=f_{3,2}=0\)，其余的为极大值，\(i=1\) 时需要特殊处理。
除此之外，也可以设 \(f_{a_1,a_2}\) 表示当前其中一个人位于 \(p_{i-1}\)，另外两个人位于 \(a_1,a_2\) 时的最小成本，转移是类似的。
给出两份代码，一个是不带方案的，一个是带的。
标签：题目,SERVICE,Service,Mobile,SP703,转移 From： https://www.cnblogs.com/high-sky/p/18546588总结：如果状态变少了，转移也得跟着变少，才能达到优化的效果。