开车旅行（算法竞赛进阶指南，倍增优化 DP）

本文主要是介绍开车旅行（算法竞赛进阶指南，倍增优化 DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.题目链接：

开车旅行

二.题目大意：

中文题有点长，就不误导大家了...

三.分析：

先预处理出一下量：

ga[i]：从城市 i 出发，小 A 下一步要到的城市.

gb[i]：从城市 i 出发，小 B 下一步要到的城市.

f[i][j][k]：从城市 j 出发，k 先走，走 $2^i$ 步后到达的城市编号.

da[i][j][k]：从城市 j 出发，k 先走，走 $2^i$ 步后，小 A 走过的距离.

db[i][j][k]：从城市 j 出发，k 先走，走 $2^i$ 步后，小 B 走过的距离.

求出上述结果后，我们就可以利用倍增以 $O(log_2x)$ 的时间复杂度求出小 A 与小 B 分别走的距离.

下面给出上述结果的求解方法.

ga[i]：从城市 i 出发，小 A 下一步要到的城市.

gb[i]：从城市 i 出发，小 B 下一步要到的城市.

倒序枚举城市 i，二分可以找出第一个高度大于等于城市 i 的城市，左右寻找即可.
void init_g()
{set < pair <ll, int> > st;st.emplace(make_pair(inf, 0));st.emplace(make_pair(inf + 1, 0));st.emplace(make_pair(-inf, 0));st.emplace(make_pair(-inf - 1, 0));for(int i = n; i >= 1; --i){auto j = st.lower_bound(make_pair(h[i], i));--j, --j;ll mn = inf, sm = inf;int mni, smi;for(int k = 0; k < 4; ++k){auto p = *j;ll d = (ll)abs(p.first - h[i]);if(d < mn){sm = mn, smi = mni;mn = d, mni = p.second;}else if(d < sm){sm = d, smi = p.second;}++j;}ga[i] = smi, gb[i] = mni;st.emplace(make_pair(h[i], i));}
}

f[i][j][k]：从城市 j 出发，k 先走，走 $2^i$ 步后到达的城市编号.

i = 0：f[0][j][0] = ga[j], f[0][j][1] = gb[j];

i = 1：f[1][j][k] = f[0, f[0][j][0], 1 - k];

i > 1：f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];
void init_f()
{for(int j = 1; j <= n; ++j){f[0][j][0] = ga[j];f[0][j][1] = gb[j];}for(int j = 1; j <= n; ++j){for(int k = 0; k <= 1; ++k){f[1][j][k] = f[0][f[0][j][k]][1 - k];}}for(int i = 2; i < N; ++i){for(int j = 1; j <= n; ++j){for(int k = 0; k <= 1; ++k){f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];}}}
}

da[i][j][k]：从城市 j 出发，k 先走，走 $2^i$ 步后，小 A 走过的距离.

db[i][j][k]：从城市 j 出发，k 先走，走 $2^i$ 步后，小 B 走过的距离.

首先定义函数 get_dist(i, j) = abs(h[i] - h[j]);

i = 0：da[0][j][0] = get_dist(j, ga[j]), da[0][j][1] = 0;

db[0][j][0] = 0, db[0][j][1] = get_dist(j, gb[j]);

i = 1：da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][1 - k];

db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][1 - k];

i > 1：da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];

db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];
int get_dist(int i, int j)
{return (int)abs(h[i] - h[j]);
}void init_d()
{for(int j = 1; j <= n; ++j){da[0][j][0] = get_dist(j, ga[j]), da[0][j][1] = 0;db[0][j][1] = 0, db[0][j][1] = get_dist(j, gb[j]);}for(int j = 1; j <= n; ++j){for(int k = 0; k <= 1; ++k){da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][1 - k];db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][1 - k];}}for(int i = 2; i < N; ++i){for(int j = 1; j <= n; ++j){for(int k = 0; k <= 1; ++k){da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];}}}
}

四.代码实现：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int M = (int)1e5;
const int N = (int)17;
const ll inf = 0x3f3f3f3f3f3f3f3f;int n;
int h[M + 5];
int ga[M + 5], gb[M + 5];
int f[N][M + 5][2];
ll da[N][M + 5][2], db[N][M + 5][2];void read()
{scanf("%d", &n);for(int i = 1; i <= n; ++i)scanf("%d", &h[i]);
}void init_g()
{set < pair <ll, int> > st;st.emplace(make_pair(inf, 0));st.emplace(make_pair(inf + 1, 0));st.emplace(make_pair(-inf, 0));st.emplace(make_pair(-inf - 1, 0));for(int i = n; i >= 1; --i){auto j = st.lower_bound(make_pair(h[i], i));--j, --j;ll mn = inf, sm = inf;int mni, smi;for(int k = 0; k < 4; ++k){auto p = *j;ll d = (ll)abs(p.first - h[i]);if(d < mn){sm = mn, smi = mni;mn = d, mni = p.second;}else if(d < sm){sm = d, smi = p.second;}++j;}ga[i] = smi, gb[i] = mni;st.emplace(make_pair(h[i], i));}
}void init_f()
{for(int j = 1; j <= n; ++j){f[0][j][0] = ga[j];f[0][j][1] = gb[j];}for(int j = 1; j <= n; ++j){for(int k = 0; k <= 1; ++k){f[1][j][k] = f[0][f[0][j][k]][1 - k];}}for(int i = 2; i < N; ++i){for(int j = 1; j <= n; ++j){for(int k = 0; k <= 1; ++k){f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];}}}
}int get_dist(int i, int j)
{return (int)abs(h[i] - h[j]);
}void init_d()
{for(int j = 1; j <= n; ++j){da[0][j][0] = get_dist(j, ga[j]), da[0][j][1] = 0;db[0][j][1] = 0, db[0][j][1] = get_dist(j, gb[j]);}for(int j = 1; j <= n; ++j){for(int k = 0; k <= 1; ++k){da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][1 - k];db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][1 - k];}}for(int i = 2; i < N; ++i){for(int j = 1; j <= n; ++j){for(int k = 0; k <= 1; ++k){da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];}}}
}void init()
{init_g();init_f();init_d();
}void cal(int s, int x, int& la, int& lb)
{la = lb = 0;for(int i = N - 1; i >= 0; --i){if(f[i][s][0] && la + lb + da[i][s][0] + db[i][s][0] <= x){la += da[i][s][0];lb += db[i][s][0];s = f[i][s][0];}}
}void work()
{int s, x;scanf("%d", &x);int la, lb;int max_h = 0, ans;double min_r = inf, r;for(int i = 1; i <= n; ++i){cal(i, x, la, lb);r = lb ? 1.0 * la / lb : inf;if(r < min_r || r == min_r && h[i] > max_h){ans = i;min_r = r;max_h = h[i];}}printf("%d\n", ans);int m;scanf("%d", &m);while((m--) > 0){scanf("%d %d", &s, &x);cal(s, x, la, lb);printf("%d %d\n", la, lb);}
}int main()
{
//    freopen("input.txt", "r", stdin);read();init();work();return 0;
}

这篇关于开车旅行（算法竞赛进阶指南，倍增优化 DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！