题目 D. Aquatic Dragon 详细题解

问题描述

有 $N$ 个岛屿排成一线，编号 $1$ 到 $N$。相邻岛屿 $i$ 与 $i+1$ 之间有一对单向水下隧道（一条 $i \to i+1$，一条 $i+1 \to i$），每条隧道最多使用一次。
初始你和龙都在岛 $1$，目标是一起到达岛 $N$。
每个岛 $i$ 上有一个神社，第一次访问时会立即将龙的体力增加 $P_i$（不耗时）。龙初始体力 $0$。
允许三种移动：

• 游泳：与龙一起移动到相邻岛，要求体力 $\ge D$，消耗 $D$ 体力，耗时 $T_s$。
• 飞行：与龙一起移动到相邻岛，要求体力 $>0$，消耗全部体力（变为 $0$），耗时 $T_f$。
• 步行：独自通过隧道走到相邻岛，不消耗体力，耗时 $T_w$，每条隧道只能使用一次。

求最小总时间。

---

关键观察与简化

1. 飞行与游泳的比较
   若 $T_f \le T_s$，则飞行总是优于或等于游泳。此时最优策略是一直飞行：从 $1$ 飞到 $2$，$2$ 飞到 $3$，…，直到 $N$。总时间 $(N-1)\cdot T_f$。
   以下假设 $T_f > T_s$。

2. 步行路径的结构
   由于每条隧道只能使用一次，步行路径不会出现重叠的区间（但可以端点相接）。
   可以将整个行程分解为若干个步骤，每个步骤对应一段步行区间 $[x, y]$（$x < y$），具体执行方式为：

   • 先从 $x$ 步行到某个端点（$y-1$ 或 $y$），再步行返回 $x$，从而第一次访问区间内所有岛屿的神社。
   • 然后将龙从 $x$ 移动到 $y$（通过游泳或飞行）。

   根据是否与下一个步骤相接，可分为三种类型：

   • 类型 1：步行到 $y-1$ 并返回，然后游泳到 $y$。
   • 类型 2：步行到 $y-1$ 并返回，然后飞行到 $y$。
   • 类型 3：步行到 $y$ 并返回，然后飞行到 $y$（此时 $y$ 的神社已被激活，下一步从 $y$ 开始）。

   若步骤以游泳结束且与下一步相接，则合并两个步骤更优，因此最优解中不会出现这种情况。所以只需考虑以上三种类型。

3. 体力变化建模
   定义前缀和

   $$Q_i = \sum_{k=1}^{i} P_k \quad (Q_0 = 0)$$

   再定义辅助数组

   $$R_i = Q_{i-1} - D \cdot (i-1) \quad (i \ge 1)$$ $$S_i = Q_i - D \cdot (i-1)$$

   考虑上一次飞行发生在从 $l-1$ 到 $l$ 的情况：

   • 若为类型 2（飞行后神社 $l$ 被激活），则到达 $x \ge l$ 时龙的体力为$$(Q_{x-1} - Q_{l-1}) - D \cdot (x-l) = R_x - R_l$$
   • 若为类型 3（飞行后神社 $l$ 已被使用过，即此前已经激活），则体力为$$(Q_{x-1} - Q_l) - D \cdot (x-l) = R_x - S_l$$

   因此定义基准值 $\text{pivot}$：

   • 类型 2 步后，$\text{pivot} = R_l$。
   • 类型 3 步后，$\text{pivot} = S_l$。

4. 执行一个步骤的条件
   设当前在岛 $x$，基准值为 $\text{pivot}$，要执行一个以 $y$ 为终点的步骤：

   • 若以游泳结束（类型 1），需要保证沿途体力非负，等价于 $R_y \ge \text{pivot}$。
   • 若以飞行结束（类型 2 或 3），需要飞行前体力 $>0$，即：
     • 类型 2：$R_{y-1} > \text{pivot} - D$。
     • 类型 3：$S_y > \text{pivot} - D$。 由于 $P_{y-1} \ge 1$，可简化判断，但原题解采用 $R_{y-1}$ 和 $S_y$。

5. 时间代价
   设步骤从 $x$ 到 $y$：

   • 若类型 1：步行往返距离 $2(y-1-x)$，耗时 $2T_w(y-1-x)$；游泳距离 $y-x$，耗时 $T_s(y-x)$。
   • 若类型 2：步行往返 $2(y-1-x)$，飞行一次 $T_f$。
   • 若类型 3：步行往返 $2(y-x)$，飞行一次 $T_f$。

   在从 $x$ 到 $y$ 的区间中，可以穿插多个类型 1 的游泳步骤（从某个 $i$ 到 $i+1$ 游泳）。设 $c$ 为满足 $x < i < y$ 且 $R_i \ge \text{pivot}$ 的 $i$ 的个数，则这些 $i$ 可以游泳通过，从而节省对应的步行时间（原本需要步行往返该段，现改为游泳一次）。因此总时间可写为：

   $$\text{time} = T_s\cdot (y-1-x) + T_f + 2T_w\cdot (y-1-x - c) + \begin{cases}0 & e'=0 \\ 2T_w & e'=1\end{cases} + dp[y][e'] $$

   其中 $e'$ 表示飞行步骤的类型（0 表示类型 2，1 表示类型 3），$dp[y][e']$ 是从 $y$ 开始到 $N$ 的最优时间。

---

动态规划定义

设

• $dp[x][0]$：当前在岛 $x$ 且与龙在一起，上一次飞行是类型 2 从 $x-1$ 到 $x$，即 $\text{pivot}=R_x$。
• $dp[x][1]$：上一次飞行是类型 3 从 $x-1$ 到 $x$，即 $\text{pivot}=S_x$。

边界：$dp[N][0]=dp[N][1]=0$（已到达终点）。
答案：$dp[1][0]$（初始状态可视为未飞行，但 $R_1 = 0$，$S_1 = P_1$，实际上需要特殊处理，但通过转移可覆盖）。

---

转移方程

对于状态 $(x,e)$，考虑下一步飞到 $y$（$y>x$），且飞行步骤类型为 $e'$。
当前 $\text{pivot} = (e==0 ? R_x : S_x)$。
条件：

• 若 $e'=0$，需 $R_y > \text{pivot} - D$，且新 $\text{pivot}' = R_y$。
• 若 $e'=1$，需 $S_y > \text{pivot} - D$，且新 $\text{pivot}' = S_y$。

设 $c$ 为满足 $x < i < y$ 且 $R_i \ge \text{pivot}$ 的 $i$ 的个数。则转移代价为：

$$ \begin{aligned} \text{cost} &= T_s\cdot (y-1-x) + T_f + 2T_w\cdot (y-1-x - c) \\ &\quad + (e'==1 ? 2T_w : 0) + dp[y][e'] \end{aligned} $$

于是

$$dp[x][e] = \min_{y> x,\ \text{条件成立}} \text{cost}$$

---

优化：减少状态枚举

直接转移是 $O(N^2)$，需要优化。
关键观察：若 $\text{pivot}' \ge \text{pivot}$，则飞行步骤可以用游泳代替（因为 $T_f > T_s$），且不会使后续条件更严格。因此我们只考虑

$$\text{pivot} - D < \text{pivot}' < \text{pivot}$$

即新基准值严格小于当前基准值，且大于当前基准值减 $D$。

所有可能的基准值只有 $2N$ 个（$R_i$ 和 $S_i$）。将状态 $(x,e)$ 按 $\text{pivot}$ 从小到大排序，依次计算 $dp[x][e]$。

维护两个线段树（对应 $e'=0$ 和 $e'=1$），每个线段树的索引 $y$ 存储：

$$\text{val}_{e'}[y] = dp[y][e'] + T_s\cdot (y-1) + 2T_w\cdot (\text{已失效的步行段数}) + \text{可能额外项} $$

具体来说，随着 $\text{pivot}$ 增大，需要：

• 将那些 $R_y < \text{pivot}$ 的 $y$ 对应的步行代价增加 $2T_w$（因为它们不能再作为游泳步骤）。
• 将那些 $R_y \le \text{pivot} - D$ 的 $y$ 从线段树中删除（设为 $+\infty$）。

通过全局偏移量加线段树区间加实现。查询时，对 $y > x$ 求最小值，然后加上 $T_s\cdot x$ 等项得到 $dp[x][e]$。计算完后将 $dp[x][e]$ 插入对应的线段树。

---

边界处理：岛屿 $N$

到达 $N$ 时，可以有两种方式：

• 最后一步是游泳到 $N$，则需满足 $S_N \ge \text{pivot}$（因为游到 $N$ 后不需要再飞行）。
• 最后一步是飞行到 $N$，则按正常转移处理。

另外，也可以完全不用飞行，全程通过步行+游泳到达。这种情况可以通过初始化时考虑 $dp[N][0/1]=0$ 并反向转移得到，或在最终答案中取 $\min$ 与直接计算。

---

算法步骤总结

1. 读入 $N, D, T_s, T_f, T_w$ 和数组 $P[1..N]$。
2. 若 $T_f \le T_s$，输出 $(N-1)\cdot T_f$，结束。
3. 计算前缀和 $Q$，再计算 $R_i = Q_{i-1} - D\cdot(i-1)$，$S_i = Q_i - D\cdot(i-1)$。
4. 建立 $2N$ 个状态 $(i,0)$ 和 $(i,1)$，分别赋予键值 $R_i$ 和 $S_i$。按键值升序排序。
5. 初始化两个线段树（大小 $N$），所有值设为 $+\infty$。将 $dp[N][0]$ 和 $dp[N][1]$ 插入对应线段树（注意插入时需考虑 $T_s$ 和 $T_w$ 的偏移）。
6. 维护一个指针，标记当前已失效的 $y$（即 $R_y \le \text{pivot} - D$），将它们在线段树中置为 $+\infty$。
7. 按排序顺序处理每个状态 $(x,e)$：
   • 更新失效指针，进行区间加（增加步行代价）。
   • 在线段树中查询 $y > x$ 的最小值，加上 $T_s\cdot x$ 等得到候选值。
   • 更新 $dp[x][e]$ 为该候选值（若多个转移取最小）。
   • 将 $dp[x][e]$ 插入对应的线段树（索引 $x$），插入值需减去相应的偏移以便后续查询。
8. 最终答案取 $dp[1][0]$（并考虑全程无飞行的可能）。

---

复杂度分析

• 排序 $O(N\log N)$。
• 每个状态处理时，线段树查询、更新均为 $O(\log N)$，总状态数 $2N$，故总复杂度 $O(N\log N)$。
• 空间 $O(N)$。

---

参考代码框架（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int N, D, Ts, Tf, Tw;
vector<int> P;
vector<ll> Q, R, S;

struct State {
    int idx, type; // type 0 -> R, 1 -> S
    ll val;
    bool operator<(const State& o) const { return val < o.val; }
};

// 线段树支持区间加、单点赋值、区间最小值
struct SegTree {
    int n;
    vector<ll> mn, lazy;
    SegTree(int sz) {
        n = 1; while (n < sz) n <<= 1;
        mn.assign(2*n, INF);
        lazy.assign(2*n, 0);
    }
    void apply(int node, ll add) {
        mn[node] += add;
        lazy[node] += add;
    }
    void push(int node) {
        if (lazy[node]) {
            apply(node*2, lazy[node]);
            apply(node*2+1, lazy[node]);
            lazy[node] = 0;
        }
    }
    void range_add(int l, int r, ll add, int node, int nl, int nr) {
        if (r < nl || nr < l) return;
        if (l <= nl && nr <= r) { apply(node, add); return; }
        push(node);
        int mid = (nl+nr)/2;
        range_add(l, r, add, node*2, nl, mid);
        range_add(l, r, add, node*2+1, mid+1, nr);
        mn[node] = min(mn[node*2], mn[node*2+1]);
    }
    void point_set(int pos, ll val, int node, int nl, int nr) {
        if (nl == nr) { mn[node] = val; return; }
        push(node);
        int mid = (nl+nr)/2;
        if (pos <= mid) point_set(pos, val, node*2, nl, mid);
        else point_set(pos, val, node*2+1, mid+1, nr);
        mn[node] = min(mn[node*2], mn[node*2+1]);
    }
    ll range_min(int l, int r, int node, int nl, int nr) {
        if (r < nl || nr < l) return INF;
        if (l <= nl && nr <= r) return mn[node];
        push(node);
        int mid = (nl+nr)/2;
        return min(range_min(l, r, node*2, nl, mid),
                   range_min(l, r, node*2+1, mid+1, nr));
    }
    void add_range(int l, int r, ll add) { if (l <= r) range_add(l, r, add, 1, 0, n-1); }
    void set_point(int pos, ll val) { point_set(pos, val, 1, 0, n-1); }
    ll query_min(int l, int r) { return range_min(l, r, 1, 0, n-1); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> D >> Ts >> Tf >> Tw;
    P.resize(N+1);
    for (int i=1; i<=N; ++i) cin >> P[i];
    if (Tf <= Ts) {
        cout << 1LL*(N-1)*Tf << '\n';
        return 0;
    }
    Q.assign(N+1, 0);
    for (int i=1; i<=N; ++i) Q[i] = Q[i-1] + P[i];
    R.resize(N+1); S.resize(N+1);
    for (int i=1; i<=N; ++i) {
        R[i] = Q[i-1] - 1LL*D*(i-1);
        S[i] = Q[i] - 1LL*D*(i-1);
    }
    vector<State> states;
    for (int i=1; i<=N; ++i) {
        states.push_back({i, 0, R[i]});
        states.push_back({i, 1, S[i]});
    }
    sort(states.begin(), states.end());
    // 线段树存储每个索引的最小候选值（已减去 T_s*(y-1) 和步行偏移）
    SegTree seg0(N+2), seg1(N+2);
    // 初始化 dp[N][0]=dp[N][1]=0
    // 插入时，需要对 y 调整：候选值 = dp[y][e'] - T_s*(y-1) - 2Tw*(something)
    // 具体实现需根据题解公式推导，此处省略细节
    // ... 
    // 最终答案 dp[1][0]
    cout << ans << '\n';
    return 0;
}

注意：上述代码仅为框架，完整实现需要仔细处理偏移量和全局步行计数。原题解已给出完整逻辑，编程时需严格按照公式实现线段树动态维护。

本题是 ICPC 区域赛难题，考察对复杂状态转移的建模、贪心优化及数据结构应用。理解体力变化与步行、游泳、飞行的关系是解题关键。