【斜率优化】【P5468】 [NOI2019]回家路线

Description

给定 \(n\) 点，这 \(n\) 个点由 \(m\) 班列车穿插连结。对于第 \(i\) 班列车，会在 \(p_i\) 时刻从 \(x_i\) 站点出发开向 \(y_i\) 站点，到站时间为 \(q_i\)。现在从 \(1\) 号节点出发，经过多次换乘到达节点 \(n\)。一次换乘是指对于两班列车，假设分别为 \(u\) 号与 \(v\) 号列车，若 \(y_u = x_v\) 并且 \(q_u \leq p_v\)，那么小猫可以乘坐完 \(u\) 号列车后在 \(y_u\) 号站点等待 \(p_v - q_u\) 个时刻，并在时刻 \(p_v\) 乘坐 \(v\) 号列车。要求最小化路程中的烦躁值。烦躁值的计算方法是：给定参数 \(A,B,C\)，对于每次等待，假设等待了 \(t\) 个时刻，那么烦躁值增加 \(A t^2 + B t + C\)。另外如果在时刻 \(T\) 到达节点 \(n\)，则狂躁值再增加 \(T\)。

Limitations

\(1 \leq n,~m \leq 2 \times 10^5\)

\(0 \leq A \leq 10,~~0 \leq B,~C \leq 10^6\)

\(1 \leq p_i \leq q_i \leq 10^3\)

保证 \(1\) 可以到达 \(n\)。

Solution

好像正解是以时间为状态DP来着……然而拿到这个题的第一反应是DP每条边到 \(n\) 的贡献。

考虑设 \(f_i\) 是第 \(i\) 条边开始出发，到达 \(n\) 号节点对烦躁值的最小贡献。于是有转移方程：

\[f_i = \min_{p_j \geq q_i} ^{x_j = y_i} \{f_j + A (p_j - q_i)^2 + B(p_j - q_i) + C + p_j - q_i\} + q_i - p_i
\]

即

\[f_i = \min_{p_j \geq q_i} ^{x_j = y_i} \{f_j + A p_j^2 - 2Ap_jq_i + Aq_i^2 + Bp_j - Bq_i + C + p_j - q_i\} + q_i - p_i
\]

将与 \(j\) 无关的项提出大括号，得到

\[f_i = \min_{p_j \geq q_i} ^{x_j = y_i} \{f_j + A p_j^2 - 2Ap_jq_i + Bp_j + p_j \} + q_i - p_i+ Aq_i^2- q_i- Bq_i + C
\]

整理得

\[f_i = \min_{p_j \geq q_i} ^{x_j = y_i} \{f_j + A p_j^2 - 2Ap_jq_i + (B+1)p_j\} + Aq_i^2- Bq_i + C- p_i
\]

设 \(g_i = A q_i^2 - Bq_i - p_i + C\)，\(h_i = Ap_i^2 + (B+1)p_j\)

上式即为

\[f_i = f_j + h_j - 2Ap_jq_i + g_i
\]

移相得到

\[f_j + h_j = 2Aq_iq_j + f_i - g_i
\]

注意到 \(g_i\) 是一个与 \(i\) 有关的常数，那么最小化 \(f_i\) 只需要最小化 \(f_i + g_i\)

如果将 \(f_j + h_j\) 看作纵坐标， \(q_j\) 看作横坐标，上述方程可以看成一条斜率为常数 \(2Aq_i\) 的直线，在所有满足条件的 \(j\) 中选择一个点，使得直线过这个点，最小化直线在 \(y\) 轴上的截距 \(f_i + g_i\)。

那么所有满足条件的点显然在一个下突壳上，证明上可以考虑如果一个点不在下突壳上那么能找到一个更优的 \(j\)。

然后考虑如果 \(i\) 会从 \(j\) 转移过来，那么一定有 \(q_i \leq p_j\)，又因为 \(p_j < q_j\)，因此 \(q_i < q_j\)，于是按照 \(q\) 的不升序进行排序即可。

在转移时，只需要在每个点维护一个凸壳表示所有可能被选择的点，然后再维护一个 set 记录该点上已经被计算但是没有插入凸壳的点。set 内部按照 \(p\) 的不升序排序，每次要转移一条边 \(i\) 的时候先将终点中 \(p\) 不小于 \(q_i\) 的边插入凸壳，由于转移是按照 \(q_i\) 的顺序进行的，已经被插入凸壳的点一定是合法可以转移的。

另外注意到 \(q_i\) 是单调不升的，于是斜率 \(2Aq_i\) 也是单调升的，再考虑到插入的横轴 \(p_j\) 也是单调不升的，因此可以使用单调队列维护每个点的凸壳即可。

需要注意的一点细节是凸壳的横轴是从大到小插入的，在维护的时候不要把大于号小于号写反。

一共进行了 \(m\) 次转移，每次转移复杂度 \(O(1)\)，因此 DP 过程的时间复杂度是 \(O(m)\)，但是由于进行了排序，且每条边插入在 set 中 1 次，所以整个算法的时间复杂度 \(O(m \log m)\)。

Code

#include <cstdio>

#include <set>

#include <queue>

#include <algorithm>

const int maxn = 200005;

const ll INF = 1ll << 50;

int n, m;

ll A, B, C, ans;

ll frog[maxn], g[maxn], h[maxn];

struct M {

  int x, y, p, q;

  inline bool operator<(const M &_others) const {

    return this->q > _others.q;

  }

};

M MU[maxn];

struct Cmp {

  inline bool operator() (const int &_a, const int &_b) {

    if (MU[_a].p != MU[_b].p) {

      return MU[_a].p > MU[_b].p;

    } else {

      return _a < _b;

    }

  }

};

std::deque<int>Q[maxn];

std::set<int, Cmp>s[maxn];

int query(const int x);

void free(const int x, const int y);

void insert(const int x, const int y);

signed main() {

  freopen("route.in", "r", stdin);

  freopen("route.out", "w", stdout);

  qr(n); qr(m); qr(A); qr(B); qr(C);

  for (int i = 1; i <= m; ++i) {

    qr(MU[i].x); qr(MU[i].y); qr(MU[i].p); qr(MU[i].q);

  }

  frog[m + 1] = 1ll << 50;

  std::sort(MU + 1, MU + 1 + m);

  for (int i = 1; i <= m; ++i) {

    g[i] = A * MU[i].q * MU[i].q - B * MU[i].q -  MU[i].p + C;

    h[i] = A * MU[i].p * MU[i].p + (B + 1) * MU[i].p;

  }

  for (int i = 1; i <= m; ++i) if (MU[i].y == n) {

    frog[i] = MU[i].q - MU[i].p;

    s[MU[i].x].insert(i);

  } else {

    int y = MU[i].y;

    free(y, MU[i].q);

    int j = query(i);

    if (!j) {

      frog[i] = INF;

      continue;

    }

    frog[i] = frog[j] + g[i] + h[j] - ((A * MU[i].q * MU[j].p) << 1);

    s[MU[i].x].insert(i);

  }

  ans = 1ll << 50;

  for (int i = 1; i <= m; ++i) if (MU[i].x == 1) {

    ans = std::min(frog[i] + A * MU[i].p * MU[i].p + B * MU[i].p + C + MU[i].p, ans);

  }

  qw(ans, '\n', true);

  return 0;

}

void free(const int x, const int y) {

  while (!s[x].empty()) {

    auto u = *s[x].begin();

    if (MU[u].p >= y) {

      insert(x, u);

      s[x].erase(u);

    } else {

      break;

    }

  }

}

inline std::pair<ll, ll> calc(const int x) {

  return std::make_pair(frog[x] + h[x], 1ll * MU[x].p);

}

inline bool judge(const int x, const int y, const int z) {

  auto i = calc(x), j = calc(y), k = calc(z);

  return (k.first <= j.first) && ((i.first - k.first) * (i.second - j.second) < (i.first - j.first) * (i.second - k.second));

}

void insert(const int x, const int y) {

  while (Q[x].size() > 1) {

    int i = Q[x].back(); Q[x].pop_back(); int j = Q[x].back();

    if (judge(j, i, y)) {

      Q[x].push_back(i); break;

    }

  }

  Q[x].push_back(y);

}

int query(const int p) {

  int x = MU[p].y;

  while (Q[x].size() > 1) {

    int i = Q[x].front(); Q[x].pop_front(); int j = Q[x].front();

    auto s = calc(i), t = calc(j); ll k = ((A * MU[p].q) << 1);

    if ((k * (s.second - t.second)) > (s.first - t.first)) {

      Q[x].push_front(i);

      break;

    }

  }

  return Q[x].size () ? Q[x].front() : 0;

}

巴特西

【斜率优化】【P5468】 [NOI2019]回家路线

Description

Limitations

Solution

Code

最新文章

热门文章