本文主要是介绍算法竞赛进阶指南 0x57 倍增优化DP，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 总论
  • AcWing\293. 开车旅行
    • part1 确定ga[], gb[]
    • part2 确定f[]
    • part3 确定da[]和db[]

前方高能！！！

总论

可以使用倍增的情况是这一种情况可以任意划分。

AcWing\293. 开车旅行

输入样例：

10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7

输出样例：

2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0

这一道题目真的是难中难！！！

注意题目中所说的“且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i 的海拔高度为 \(H_i\)。”.注意这些城市并不是排列在同一条线上，可能是1号到3号的距离更近。但是总体上的趋势是往东走。

现在思考，对于每一个点，都会向东走，走到距离最小或者是最小的地方。

由于：

1. 各个城市的海拔高度互不相同
2. 当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近

所以每一个点（无论是A开车还是B开车）到达的下一个点的位置是固定的。SO？如果确定了起始点，那么所走的路线是唯一固定的。

part1 确定ga[], gb[]

由于最大值与最小值是在目前所处的点的东方，所以遍历的时候从右向左。遍历完一个就加上值。

使用set来求邻值。

对set的使用方法进行分析：

邻值肯定在与当前值最近的地方。如果最近的是2，那么次近的就是1或者3. 反之，如果最近的是3，那么次近的是2或者4.

所以只需要关注离他最近的这是个值。

为了方便，可以在set中存入两个正无穷以及两个负无穷！
注意：由于set不能含有相同的元素，所以两个“正无穷”不能相等

注意：0x3f3f3f3f不一定可以代表正无穷！他的值是1,061,109,567，大概是\(10^9\)，当可能存在的最大值大于\(10^9\)时，应该选择其他最大值，甚至是选择long long。

part2 确定f[]

对于f[]的确定，代码不是太难，重点是要学会使用倍增求出。

f[i][j][k]表示从j出发，k先开车，走过\(2^i\)所到达的位置。
k == 0表示小A开车

1. 显然f[0][j][0] = ga[j]，f[0][j][1] = gb[j]
2. 当j==1，有(注意：与3不同的原因是\(2^1\)的一半不再是偶数，初始开车的人不同)
   f[1][j][0] = f[0][ f[0][j][0] ][1]（先小A开一下，然后小B在小A开到的位置继续开。
   f[1][j][1] = f[0][ f[0][j][1] ][0]
3. 当j > 1，有
   f[i][j][0] = f[i-1][ f[i-1][j][0] ][0]
f[i][j][1] = f[i-1][ f[i-1][j][1] ][1]

f 的第一维的确定：由于使用倍增。而\(2^{16} =65,536\)所以17已经够使用。

part3 确定da[]和db[]

同样需要找到转移关系。

da[i][j][k]表示从j出发，k先开车，走过\(2^i\)，小A所走过的所有距离。
db[i][j][k]表示从j出发，k先开车，走过\(2^i\)，小B所走过的所有距离。

与上面相同，分为一下三种情况：

1. da[0][j][0] =

这篇关于算法竞赛进阶指南 0x57 倍增优化DP的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！