Visits: 683

双调巡游

这道题我在网上找到了很多解法

大体上还是分类讨论的，分i>j+1、i=j+1等情况

不过我觉得完全没有必要考虑这么多，这样考虑太复杂了

换一个角度，不要按照网上那么多的情况去考虑，换一种更简单的思路

其实状态转移方程很简单，不需要分类讨论的

首先明确，一个人从最左边开始走，走到最右边，然后回来，需要走的路程，等价于两个人同时从最左边的点开始沿着两条不同的路走到最右边汇合的距离的和

还是定义一个状态dp[i][j]表示第1个人在i、第2个人在j，走到汇合点至少需要走的距离和

那么显然$$ \forall i,j 有 dp[i][j]=dp[j][i]恒成立$$

如果附加一个条件，每个人只要走到了点x，那么比x更左边的点必须也走过

这样，取i和j中较大的一个，记为x，这意味着，所有小于x的点，要么被第1个人走过，要么被第2个人走过，不可能两个人都不走过

在这个附加条件下，如果第1个人在i，第2个人在j，下面要继续下一步的行动，受到这个条件的约束，显然只可能有2种走法

• 要么第1个人从i走到x+1
• 要么第2个人从j走到x+1

也就是说

一个人在i，另一个人在j，他们汇合还需要走的距离和dp[i][j]

• 要么是等于一个人在x+1而另一个人还在i时候的dp[i][x+1]，加上那个人从x+1走回j需要的distance(j,x+1)
• 要么是等于一个人在x+1而另一个人还在j时候的dp[x+1][j]，加上那个人从x+1走回i需要的distance(i,x+1)

dp[i][j] = dp[x + 1][j] + distance(i, x + 1)
或者
dp[i][j] = dp[x + 1][i] + distance(j, x + 1)

上面已经说了，dp[i][j]=dp[j][i]恒成立

事实上也无关乎哪个人在哪里，两个人是无差别的

所以不妨始终计算i>j的那一半

于是，上面的代码就是

dp[i][j] = std::min(dp[i + 1][j] + distance(i, i + 1), dp[i + 1][i] + distance(j, i + 1));

两种走法里面挑较短的一个就是状态转移

考虑边界

显然，如果两个人里面已经有一个在汇合点了

那么根据上面的约束条件，汇合点是最右边的点，所以所有它左边的点都被它走过一遍了

那么不管另一个人在哪里，他都没有必要再去走其他的点，只要直奔汇合点就可以汇合了

而直奔汇合点的距离显然是最短的

那么，所有的边界条件就是

dp[n - 1][i] = distance(i, n - 1);

至此，完整的状态转移方程就变得非常简单

for (int i = 0; i < n - 1; ++i) {
    dp[n - 1][i] = distance(i, n - 1);
}

for (int i = n - 2; i >= 0; --i) {
    for (int j = 0; j <= i; ++j) {
        dp[i][j] = std::min(dp[i + 1][j] + distance(i, i + 1), dp[i + 1][i] + distance(j, i + 1));
    }
}

最后要输出的结果就是dp[0][0]，即两个人都在最左边的点，要汇合，至少要走多少路

代码中用到的distance()是求两个点的直线距离，sort和comp是用来把点从左到右排序的，这部分代码比较简单，就不详细说明了

注意一个坑

因为数据范围比较大，开double[][]的二维数组可能会爆内存（可能，或者是Memory Limit Exceeded，或者是Runtime Error，当然也可能什么事都没有）

题目只要求精确到0.001，所以我只开了float[][]

下面给出完整代码