作业|学习资料|算法|题解

双调巡游

凝神长老 · 5月5日 · 2018年 · 1508次已读

本文写于 2018年05月05日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


双调巡游

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

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

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

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

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

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

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

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

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

这样,取ij中较大的一个,记为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()是求两个点的直线距离,sortcomp是用来把点从左到右排序的,这部分代码比较简单,就不详细说明了

注意一个坑

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

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

下面给出完整代码

此区域的内容仅评论后可见
0 0 投票
Article Rating
订阅评论动态
提醒
guest
19 评论
最新
最旧 得票最多
行内反馈
查看所有评论
长安有故里
长安有故里 Chrome 83.0.4103.97 Windows 10
2020年06月17日 19:17

多谢大佬
 

yutau
yutau Chrome 81.0.4044.138 Mac OS X 10_15_4
2020年05月14日 08:22

tql!

Nan
Nan Chrome 81.0.4044.129 Windows 10
2020年05月03日 23:47

tql!

Bai
Bai Edge 18.18362 Windows 10
2020年05月03日 20:01

tql!

yjt
yjt Firefox 74.0 Windows 10
2020年05月03日 17:58

tql!

hly
hly Chrome 81.0.4044.129 Windows 10
2020年05月01日 16:05

tqqqqql

slijfll
slijfll Chrome 81.0.4044.122 Mac OS X 10_13_6
2020年04月29日 19:37

看一下!!

Kuroko
Kuroko Chrome 81.0.4044.122 Windows 10
2020年04月25日 18:13

Orz 前来抄作业

huyu
huyu Edge 17.17134 Windows 10
2019年06月18日 20:36

tql

phenom
phenom Chrome 73.0.3683.103 Windows 8
2019年04月20日 20:38

tql

deerbean
deerbean Chrome 66.0.3359.181 Windows 10
2019年04月16日 15:25

自己写疯狂爆内存,哭了

xiaocaiji
xiaocaiji Chrome 73.0.3683.103 Windows 10
2019年04月14日 17:57

tql

humpy
humpy Chrome 73.0.3683.86 Windows 10
2019年04月11日 12:53

讲的明明那么简单明白,但是我还是写出了一大片WA…… 很是惭愧-_-#

humpy
humpy Safari 604.1 iPhone iPhone OS 12_2 like Mac OS X) AppleWebKit
回复  凝神长老
2019年04月20日 09:18

后来我重新认真看了一下题目,发现是没注意取值范围,用int存储坐标的话在算距离的时候可能会溢出。改了一下就过啦。

raw
raw Chrome 73.0.3683.86 Mac OS X 10_12_6
2019年04月09日 16:11

tqqqqql

caiji
caiji Chrome 73.0.3683.86 Windows 10
2019年04月08日 17:22

tql

dscs
dscs Chrome 73.0.3683.86 Windows 10
2019年04月04日 19:04

tql