2016微软探星夏令营在线技术笔试题解(4
题目大意：
有N个不同的建筑物之间有M条道路相连，道路的设计保证任意两个城市之间都是连通的，并且通过每条道路都需要花一定的时间。同时有Q个不同的工作分布在这N个建筑物中，每份工作给出了工作所在的位置、最早和最晚的开始时间以及工作需要花费的时间，最后给出了完成工作后可以得到的报酬。
现假设在0时刻LittleHu在1号建筑物，题目要求通过合理地安排工作方案，LittleHu可以得到的最多的报酬。
解答：
本题难度较大，考查了算法的综合使用。本题结合了图算法、状态压缩以及动态规划的知识。基本思路是：首先对于任意的两份工作，计算出从其中一份工作所在的地点到另一份工作所在的地点所走过的最短路径，然后在通过状态压缩和动态规划的思想求得本题的最优解。具体解法如下：
·最短路径：
由于每份工作都规定了工作开始的最早和最晚的时间，如果到达工作所在地点的时候，时间已经超过了工作最晚开始的时间，那么该工作就无法完成。因此，基本的思路就是：尽可能少地将时间花在路上的移动过程。因此我们需要知道任意两个建筑物之间的最短距离，使得路上花费的时间尽可能少。由于并不是每一座建筑物内都有工作安排，因此，我们仅需要知道在有工作安排的建筑物之间切换时的最短路径就可以了。计算最短路径可以使用经典的迪杰斯特拉(dijkstra)算法。以每一个有工作安排的建筑作为源点计算一次。
经典的迪杰斯特拉算法的时间效率为O(n2),可以采用堆堆算法进行优化，使得整个算法的效率为O(nlgn)。
可以采用一个Q×Q的矩阵来存储最短路径的数据，元素记录了从编号为i的工作的地点移动到编号为j的工作的地点所需要的最少的时间。
·状态压缩：
在计算出最短路径后，我们采用动态规划的方式计算结果。首先要做的是定义状态。这里的状态涉及到了选择哪些工作完成，同时还涉及到了以什么样的顺序完成这些工作。这里采用一个Q位的二进制数来标记哪些工作被完成：对于第i位二进制位，如果该位是0，表示编号为i的工作没有完成，如果是1，则表示编号为i的工作已经完成。为了记录工作完成的顺序，我们需要记录当前最后完成的工作的编号。定义状态如下：
需要说明的是：对于dp[s][k]中的状态s，如果它的第k为二进制位的为0，那么dp[s][k]一定是非法的。因为既然当前状态下最后完成的工作为k号，那么也就意味的k号工作一定已经完成，因此状态s中的表示k号工作的第k为二进制位的一定是1。
·动态规划：
定义状态后，我们还需要知道状态的转移方式。对于dp[s][k]，当我们得到它的时，表明当前的状态为：完成工作的状态是s，并且最后完成的工作为k号工作。接下来的策略就是，继续选择目前尚未完成的工作，移动到该工作的地点，然后完成工作。此时，就转移到了下一个状态。
对于当前状态到底哪些工作还没有完成，则取决于状态s，s中哪些为0的二进制位，就表示对应的工作尚未完成。
假设当前状态下，编号为m的工作尚未完成，此时，我们需要进行以下步骤：
首先需要移动到工作m的所在地点，由于当前状态下，最后完成的工作时工作k，所以需要从工作k的地点移动到工作m的地点，花费的时间是。
然后完成工作m，花费是时间是给定的工作m需要花费的时间。
然后更新状态s，标记工作m已经完成，即此时，将s中的第m为二进制位为1，我们用按位或运算完成状态的更新。新的状态：
总最后完成的工作就是工作m，因此新的状态就是:，于是，我们利用dp[s][k]的结果得到了dp[s_new][m]，具体dp[s_new][m]的，则分为以下的几种情况：
①当到达工作m的地点时，时间已经超过了工作m的最晚开始时间E(m)，即：
表示当前工作无法完成，该方案不可行，因此不需要更新dp[s_new][m]。
②当到达工作m的地点时，时间要比工作m的最早开始时间S(m)还要早，即：
表示当前情况为提前到达，需要等待，到时间S(m)时才可以开始工作。因此，工作完成时的时间为：,此时需要更新的，比较当前计算结果和dp[s_new][m]的原始，保留较小者：
③当到达工作m的地点时，时间介于S(m)和E(m)之间，即：S(m)≤dp[s][k]dist[k][m]≤E(m)表示此时可以立刻开始进行工作m，花费时间同样是T(m)，完成后的时间为：
此时和情况②类，也需要更新的：
以上为状态转移的规则。
需要说明的是：dp[s][k]中s的范围是0-(2^Q-1),k的范围则是1-Q。对于工作数目Q数较大的情况，在通过动态规划计算结果时，要处理的数据量也会呈指数式增长。所以，在某些情况下，这个过程的效率非常低。
·初始化和迭代顺序：
在进行状态转移前，需要一个初始的状态，这里我们可以定义一个“冗余”的工作。它的工作地点就在最开始的起点：建筑1，同时，为了不影响计算结果，它的最早开始时间，最晚开始时间，持续时间以及工作的报酬均置为0，该工作的编号也记为0，并且该工作不需要再状态s中记录，即此时工作的数目为Q1，但s依旧是一个Q位的二进制数。
此时，完成工作0所需的最小时间就是0，这种情况最后完成的是工作0，并且其他的工作还都没有完成，即：在状态转移过程中，由于每次状态转移过程都会使得完成的工作数目增加，因此我们的计算顺序由dp[s][k]中的状态s决定。这里的迭代顺序取决于s中二进制位为1的位置的数目。首先处理只有1位二进制位为1的所有状态s的情况，然后处理2个1的情况、3个1的情况......这里可以使用队列来保证迭代顺序的正确性，每次迭代取出队列首部的元素，同事将计算过程中转移到的新状态加入到队列中。
·计算结果：
动态规划计算过程完成后，我们通过遍历所有的状态dp[s][k]，如果dp[s][k]的结果不是-1，表明当前的方案是可行的，然后根据状态s计算可以得到的报酬，最后输出得到的最大即可。
以上是本题的解答思路。
输入输出式：
备注：
本题的数据基数比较大，题目中工作的数目Q最大为20，地点数N最大是10000，在这种情况下，动态规划的搜索空间是：2^20×20，这是一个庞大的数字。因此，本题在某些情况下会卡算法时间效率的常数因子。
程序处理的每一个环节和步骤，必须要尽可能的达到最高的效率，否则，即使是同样的解题思路，有些程序代码提交后同样会超时。笔者就是比较悲催的后者
推荐：