7.倍增优化dp

发表于 分类于 ， 本文字数： 1k

倍增优化DP通常会将2^k 中的k压入状态方程之中，以表示状态方程其他状态满足某种倍增性质时的结果，例如下面的两个例子，跑路中的dp[i][j][k]可以表示i，j两点之间是否存在一条路径长度为2^k 的路径，开车旅行中的Fun[who][city][k]可以表示who先开，从city出发，开2^k天可以到达的城市。

而转移方程，毫无疑问也与倍增相关，转移方程中，最外层的循环几乎都是循环与倍增有关的变量——k，这一点上可以类比区间动态规划的思想，都是从短(小)的循环到长(大)的。

img

求家到公司的最短时间，稍微思考一下，发现是求图上两点最短路的变种板，即从原来的最短路，变成了求最短时间，而两者之间的联系——速度（广义），并不是一个恒定值，而是满足于一个规律，即跑2^k m只要一秒，其他距离通过2^k的模式进行合并。

转换转换思维，求两点之间的最短路，需要一个单位进行度量，在这道题中是秒，因此我们要把所有可以在一个单位时间内跑完的路径求出作为求最短路之前的准备工作，进而求出其他需要大于一个单位时间内跑完的路径。

发现数据量并不大，所以可以使用Floyd算法。

于是我们得到状态方程dp[i][j]，表示从i跑到j所需要的最少时间。

那首先是初始化，即上面所说的将所有可以在一个单位时间内跑完的路求出。由于题目给出的都是距离为1(2^0)的点，所以所有可以一个单位时间内跑完的路径2^k一定都可以由两个2^(k - 1)的路径组成，这里就用到了倍增优化的思想（虽然感觉关系不大），于是我们可以类比区间动态规划的思想，从最短的“一单位”路径枚举到最长的“一单位”路径，所以我们可以得到以下方程

1
2
3
4
5
6
7
8
9
for(int k = 0; k < 节点数量; k++)
for(int t = 0; t < 节点数量; t++)
for(int i = 0; i < 节点数量; i++) 
for(int j = 0; j < 节点数量; j++) 
	if (G[i][t][k - 1] && G[k][j][k - 1]) {
		G[i][j][k] = true;
		dp[i][j] = 1;
	}
//G[i][j][k]表示i到j有2^k的路径吗

也可以得到转移方程（Floyd的算法）

1
for(int k = 0; k < 节点数量; k++) for(int i = 0; i < 节点数量; i++)  for(int j = 0; j < 节点数量; j++)  dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏