Codeforces-1601B: Frog Traveler
题目
题目传送门：codeforces1601B
题目截图
样例描述
样例解释：第一个例子是从井底深3米处起跳，因此跳 a 3 = 2 a_3=2 a3=2米，到达深1米的地方，掉落 b 1 = 1 b_1=1 b1=1米，于是起跳点变成了2米深的地方，之后再跳 a 2 = 2 a_2=2 a2=2米，就可以跳到地面上。
题目大意
Gorf先生正在旅行，不幸的是在一次跳跃中它掉到了深
n
n
n 米的井里。现在它在井的底部，有很高的距离要跳。但井的表面的平滑程度是不均匀的，有的地方很光滑，有的地方又很容易起跳。即，在地面下
x
x
x 处，它一次只能跳
[
0
,
a
x
]
[0, a_x]
[0,ax] 米，且它不想往下跳。
不幸的是，Gorf先生年老体弱，在每次跳以后得歇一下，也就是跳到
x
x
x后，它会下滑
b
x
b_x
bx的距离，求Gorf先生跳到地面的最少跳跃次数，并输出每次跳跃到达的深度（在没有下滑之前）。
题目解析
深度从
n
n
n 到
0
0
0 开始考虑，设
d
p
[
i
]
dp[i]
dp[i] 代表从
0
0
0 到
i
i
i 的最小走的步数（下滑后）。
那么其实对于每个起始位置
x
x
x ，它能跳到的位置是
{
s
}
=
{
x
+
b
[
x
]
.
.
.
x
−
a
[
x
]
+
b
[
x
−
a
[
x
]
]
}
\{s\}=\{x+b[x]...x-a[x]+b[x-a[x]]\}
{s}={x+b[x]...x−a[x]+b[x−a[x]]}，那么转移方程就变成了
d
p
[
i
]
=
min
(
d
p
[
x
]
+
1
,
d
p
[
i
]
)
,
i
∈
{
s
}
dp[i]=\min (dp[x]+1, dp[i]), i \in \{s\}
dp[i]=min(dp[x]+1,dp[i]),i∈{s}。其实这个最小值是对一段连续的序列更新的，所以可以用线段树的lazy标记顺序向浅层更新一段序列的最小值，这个复杂度是
O
(
n
log
n
)
O(n \log n)
O(nlogn)的。
但其实这道题还有
O
(
n
)
O(n)
O(n)的做法。考虑更新到
x
x
x 的时候，此时前面
x
+
1
,
.
.
.
,
n
x+1,...,n
x+1,...,n的
d
p
dp
dp 值已经被更新了，而如果我们更新完
x
x
x（作为起跳点） ，从
x
x
x 到
x
x
x 能到达的深度最浅的地方
y
=
x
−
a
[
x
]
y=x-a[x]
y=x−a[x] i.e. [x, …, x-a[x]] ，其实
d
p
dp
dp 值已经确定了。更一般地，我们不需要更新历史能到达深度以内的位置
d
p
dp
dp 值，因为如果假设
y
y
y是
x
x
x及其之前能到达的位置，那么
d
p
[
y
]
dp[y]
dp[y] 在
[
x
+
1
,
.
.
.
y
−
1
]
[x+1,... y-1]
[x+1,...y−1] 这一段更新时，最好情况也不会比
x
x
x或
x
x
x之前到达
y
y
y所用的最短步数少。关于这一点，可以用一个大致图来表示（没有画一步一步，而是几步几步，以便说明）：
这张图表明，首先更新步长为
1
1
1 的结点时，肯定是先更新从开头连续的一小段。之后，每个结点下滑一段距离，如果下滑后的结点不能跳到橙色区域，那么往后肯定不会是最优步数，因为本可以一步跳到对应位置。如果能跳到橙色区域（需要两步跳到），由于每次可以选择一段连续的区间作为落地点，所以扩展出的橙色区域是二次起跳后落地点的最大并集，也是连续的。依此类推，其实最终我们得到的最少次数分布（只考虑下滑前的位置），是以一些连续的段呈现的（不考虑无法到达的位置），且这些段从开始到结束次数不断顺序
+
1
+1
+1。当然，这并不意味着
d
p
dp
dp 值是连续的，因为也会有如
a
i
a_i
ai 和
b
i
b_i
bi 都很大的情况，也就是跳到
i
i
i 会直接跌落井底，从
i
i
i 跳能直接跳到地面的情况。但这种未下滑前的落地点的连续性，可以帮我们在计算时，把大量不需要更新的点去除掉，只更新有可能的点。
其实也可以用图论来考虑这道题，除了能直接到达地面的位置（这些位置直接连终止点），其余，给每个落脚点（下滑后）建一个长度为
1
1
1 的边，那么直接建一个图（过程需要上面结论和一些其它减少边数的方式），求解最短路径即可。而上一种的做法其实本质思想也类似于Dijkstra求最短路，因为先更新下滑前落地所需步数最短的结点，只不过这个更新结点，在入队的时候需要的步数随入队顺序会不断递增，因此不需要堆或优先队列。
Code
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 3e5 + 7;
int a[maxn], b[maxn], dp[maxn], q[maxn], stk[maxn], stand[maxn], jump[maxn];
int main(){
int n, x, v, up;
int l = 0, r = 0, top=0, upside=inf;
memset(dp, 0x3f, sizeof(dp));
cin >> n;
for(int i=1; i<=n; ++i) cin >> a[i];
for(int i=1; i<=n; ++i) cin >> b[i];
dp[n] = 0; q[r++] = n; stand[n] = n; jump[n] = n;
while (r > l) {
x = q[l++];
for(int i=a[x]; i>=0; --i) {
up = x - i; v = up + b[up];
if (up <= 0) {dp[0]=min(dp[0], dp[x]+1);stand[0] = x;r=l-1;break;}
if (up >= upside) break;
if (v <= n && dp[v] > dp[x] + 1) {
dp[v] = dp[x] + 1; q[r++] = v;
stand[v] = x; jump[v] = i;
}
}
upside = min(upside, x - a[x]);
}
if (dp[0] > n) cout << -1 << endl; else {
cout << dp[0] << endl;
x = 0;
while(x != n) {
v = stand[x] - jump[x];
stk[top++] = v;
x = stand[x];
}
for(int i=top-1; i>=1; --i) cout << stk[i] << " ";
cout << 0 << endl;
}
return 0;
}