https://www.acwing.com/problem/content/description/331/
貌似只能够从下往上反推，从上往下不知道走哪个方向好。每次找出这个平台A下落到哪个平台B，再从B的左右端点向上转移。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 200001; short st[MAXN * 4 + 5], lazy[MAXN * 4 + 5]; inline void PushDown(int o) { if(lazy[o]) { lazy[o << 1] = lazy[o]; st[o << 1] = lazy[o]; lazy[o << 1 | 1] = lazy[o]; st[o << 1 | 1] = lazy[o]; lazy[o] = 0; } } void Update(int o, int l, int r, int ql, int qr, int v) { if(ql <= l && r <= qr) { lazy[o] = v; st[o] = v; return; } PushDown(o); int mid = l + r >> 1; if(ql <= mid) Update(o << 1, l, mid, ql, qr, v); if(qr >= mid + 1) Update(o << 1 | 1, mid + 1, r, ql, qr, v); } int Query(int o, int l, int r, int x) { if(l == r) return st[o]; PushDown(o); int mid = l + r >> 1; if(x <= mid) return Query(o << 1, l, mid, x); return Query(o << 1 | 1, mid + 1, r, x); } const int P = 100001; int dpL[30005], dpR[30005]; int L[30005], R[30005]; int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif int n, s; scanf("%d%d", &n, &s); s += P; L[0] = P, R[0] = P; for(int i = 1; i <= n; ++i) { scanf("%d%d", &L[i], &R[i]); L[i] += P, R[i] += P; int ql = Query(1, 1, MAXN, L[i]); dpL[i] = min(dpL[ql] + abs(L[i] - L[ql]), dpR[ql] + abs(L[i] - R[ql])); int qr = Query(1, 1, MAXN, R[i]); dpR[i] = min(dpL[qr] + abs(R[i] - L[qr]), dpR[qr] + abs(R[i] - R[qr])); Update(1, 1, MAXN, L[i], R[i], i); } printf("%d\n", min(dpL[n] + abs(s - L[n]), dpR[n] + abs(s - R[n]))); }AcWing - 329 - 围栏障碍训练场 = 线段树 + dp
标签：
原文地址：https://www.cnblogs.com/Inko/p/11600135.html