正題

luogu 7599[APIO 2021 T2]

---

題目大意

給你一排樹中每棵樹的高度，每次跳躍可以跳到左/右邊第一棵比該樹高的樹，問你從A-B中某棵樹跳到C-D中的某棵樹的最小步數（$A?B<C?D$）

---

解題思路

上圖為例，綠色為起點，藍色為終點

對于起點，不難發現，要選擇低于最高終點的點中盡量高度，且右邊的起點都比它低

低于最高終點保證了可以跳到終點，而最高的保證了跳的步數盡可能少，如果右邊有比它高的，通過前面的性質，可以發現無法跳到終點（用倍增實現）

起點確定之后考慮往左右跳，由于$A?B<C?D$，往終點走一定是往右跳

那么往左有什么意義呢，對于4,2,3,4,5，當位于2時，往右跳到5要3步，而先往左跳一步只要兩步，由此，往左跳的高度如果大于右邊若干樹的高度，那么往左跳可以使答案跟優

那么把跳躍分成往上和往右兩步，設$f{j}_{i,j}$為位于i向上跳$2^j$步的最高高度，因為跳到右邊可以使往右跳少一步，所以往上跳一定能使往右跳步數減少，且跳得越高，少得越多

所以往上跳跳到第一個點，使得該點高于起點終點之間的所有點，然后往右跳即可

---

代碼

#include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define NN 200021 using namespace std; int n, m, v, x, A, B, C, D, lg, bg, hed, top, ans; int h[NN], d[NN], lj[NN][20], rj[NN][20], hj[NN][20]; struct node {int v, s;bool operator <(const node &b) const{return s > b.s;} }b[NN]; struct Tree//線段樹找最大 {int a[NN<<2];#define ls x*2#define rs x*2+1void build(int x, int l, int r){if (l == r){a[x] = h[l];return;}int mid = l + r >> 1;build(ls, l, mid);build(rs, mid + 1, r);a[x] = max(a[ls], a[rs]);return;}int ask(int x, int L, int R, int l, int r){if (L == l && R == r) return a[x];int mid = L + R >> 1;if (r <= mid) return ask(ls, L, mid, l, r);else if (l > mid) return ask(rs, mid + 1, R, l, r);else return max(ask(ls, L, mid, l, mid), ask(rs, mid + 1, R, mid + 1, r));} }T;void init(int N, std::vector<int> H) {n = N;int lg = log2(n);for (int i = 1; i <= n; ++i){h[i] = H[i - 1];b[i].v = i;b[i].s = h[i];lj[i][0] = i;for (int j = 1; j <= log2(i); ++j)//向左跳，找起點，存的是最高高度if (h[lj[i][j - 1]] > h[lj[i - (1<<(j - 1))][j - 1]]) lj[i][j] = lj[i][j - 1];else lj[i][j] = lj[i - (1<<(j - 1))][j - 1];}for (int i = 1; i <= n; ++i)//向高跳{while(h[d[top]] < h[i] && top) top--;hj[i][0] = d[top];d[++top] = i;}top = 0;for (int i = n; i > 0; --i){while(h[d[top]] < h[i] && top) top--;if (h[hj[i][0]] < h[d[top]]) hj[i][0] = d[top];rj[i][0] = d[top];for (int j = 1; j <= lg; ++j)//向右跳rj[i][j] = rj[rj[i][j - 1]][j - 1];d[++top] = i;}sort(b + 1, b + 1 + n);for (int i = 1; i <= n; ++i)for (int j = 1; j <= lg; ++j)hj[b[i].v][j] = hj[hj[b[i].v][j - 1]][j - 1];//倍增T.build(1, 1, n); }int minimum_jumps(int A, int B, int C, int D) {A++;B++;C++;D++;lg = log2(n);hed = T.ask(1, 1, n, C, D);if (B + 1 <= C - 1) v = T.ask(1, 1, n, B + 1, C - 1);else{if (h[B] < hed) return 1;return -1;}if (v > hed) return -1;x = B;bg = B;for (int i = lg; i >= 0; --i)if (h[lj[x][i]] <= hed && x - (1<<i) + 1 >= A){if (h[bg] < h[lj[x][i]]) bg = lj[x][i];//找起點x -= (1<<i);}ans = 0;for (int i = lg; i >= 0; --i)if (hj[bg][i] && h[hj[bg][i]] < v){bg = hj[bg][i];//向高跳ans += (1<<i);}if (hj[bg][0] && h[hj[bg][0]] < hed && h[bg] < v){bg = hj[bg][0];ans++;}for (int i = lg; i >= 0; --i)if (rj[bg][i] && rj[bg][i] < C)//向右跳{bg = rj[bg][i];ans += (1<<i);}if (h[bg] <= hed) return ans + 1;else return -1; }

總結

以上是生活随笔為你收集整理的【倍增】【线段树】雨林跳跃（luogu 7599[APIO 2021 T2]）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。