[SDOI2012] 基站建设

GitHub跳转原题关系图返回列表

把每个点看成按 x 坐标有向无环图上的一个状态，接收费用可整理成关于目标坐标 x 的直线，用 Li Chao Tree 维护左侧所有可转移点的最小值。

OJ: luogu

题目 ID: P2497

难度:省选/NOI-

标签:动态规划几何Li Chao Tree最短路

日期: 2026-06-21 06:57

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

一条直线上有若干个点：

  • 最左边是移动公司
  • 中间一些点是基站
  • 右边某个位置是 up 主家

每个点 i 有：

  • 位置 x_i
  • 发射半径 r_i
  • 启动费用 v_i

如果点 i 要从左边某个点 j 接收信号，那么必须满足两个圆相切，对应要额外付出接收费用 sqrt(r'_i)。

目标是用最小总代价，让某个能覆盖 up 主家的点接收到信号，并把信号继续传到 up 主家。

思路

先看一个小数据朴素 DP：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;
const long double INF = 1e100L;

struct Node {
    long long x, r, v;
} a[MAXN];

int n;
long long home_x;
long double dp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：朴素 DP。
    // 直接枚举前一个被选中的基站，做 O(n^2) 的最短路转移。
    cin >> n >> home_x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].r >> a[i].v;
    }

    sort(a + 1, a + n + 1, [](const Node &lhs, const Node &rhs) {
        if (lhs.x != rhs.x) {
            return lhs.x < rhs.x;
        }
        if (lhs.r != rhs.r) {
            return lhs.r < rhs.r;
        }
        return lhs.v < rhs.v;
    });

    for (int i = 1; i <= n; i++) {
        dp[i] = INF;
    }
    dp[1] = (long double) a[1].v; // 第一个点就是移动公司。

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (dp[j] >= INF / 2 || a[j].x >= a[i].x) {
                continue;
            }
            long double extra = (long double) (a[i].x - a[j].x)
                              / (2.0L * sqrtl((long double) a[j].r));
            dp[i] = min(dp[i], dp[j] + extra + (long double) a[i].v);
        }
    }

    long double ans = INF;
    for (int i = 1; i <= n; i++) {
        if (llabs(a[i].x - home_x) <= a[i].r) {
            ans = min(ans, dp[i]);
        }
    }

    cout.setf(ios::fixed);
    cout << setprecision(3) << (double) ans << '\n';
    return 0;
}

把所有点按 x 从小到大排序。

设 dp[i] 表示：

“把第 i 个点启动，并且让它成功从左边收到信号”的最小总代价。

第一个点就是移动公司本身，所以：

dp[1] = v_1

若 j < i，那么从 j 向 i 传信号时，几何条件是两个圆相切。

因为发送圆半径固定为 r_j，接收圆半径可调，且圆心都在地面上，所以有：

(x_i - x_j)^2 = 4 * r_j * r'_i

于是：

sqrt(r'_i) = (x_i - x_j) / (2 * sqrt(r_j))

这就是从 j 向 i 传信号的额外接收费用。

因此转移为：

dp[i] = v_i + min( dp[j] + (x_i - x_j) / (2 * sqrt(r_j)) )

把和 i 有关的部分展开：

dp[i] = v_i + min( dp[j] - x_j / (2 * sqrt(r_j)) + x_i / (2 * sqrt(r_j)) )

对固定的 j 来说，这是关于 x_i 的一条直线：

y = k_j * x_i + b_j

其中：

  • k_j = 1 / (2 * sqrt(r_j))
  • b_j = dp[j] - k_j * x_j

所以问题变成：

按 x 从小到大枚举每个点 i，查询所有左侧点对应直线在 x_i 处的最小值。

这正是 Li Chao Tree 的标准应用。

最后，只要某个点的发射圆能覆盖 up 主家，也就是满足：

|x_i - home_x| <= r_i

那么就可以用 dp[i] 更新答案。

DP 转移方程

核心状态：

dp[i] 为启动 i 并接收到信号的最小总代价

核心转移：

dp[i]=v_i+min(k_j*x_i+b_j)

答案收束：

能覆盖家的点里取最小 dp[i]

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const long double INF = 1e100L;

struct Node {
    long long x, r, v;
} a[MAXN];

struct Line {
    // y = kx + b
    long double k, b;
    bool empty;
} seg[MAXN << 2];

int n;
long long home_x;
long long coord[MAXN];
int coord_cnt;
// dp[i]：把第 i 个点启动，并让它收到来自左边的信号的最小代价。
long double dp[MAXN];

long double value(const Line &line, long long x) {
    return line.k * (long double) x + line.b;
}

void insert_line(int idx, int l, int r, Line line) {
    if (seg[idx].empty) {
        seg[idx] = line;
        return;
    }

    int mid = (l + r) >> 1;
    long long xl = coord[l];
    long long xm = coord[mid];
    long long xr = coord[r];

    Line low = seg[idx];
    Line high = line;
    if (value(low, xm) > value(high, xm)) {
        swap(low, high);
    }
    seg[idx] = low;

    if (l == r) {
        return;
    }

    if (value(low, xl) > value(high, xl)) {
        insert_line(idx << 1, l, mid, high);
    } else if (value(low, xr) > value(high, xr)) {
        insert_line(idx << 1 | 1, mid + 1, r, high);
    }
}

long double query_min(int idx, int l, int r, int pos) {
    long double ans = INF;
    if (!seg[idx].empty) {
        ans = value(seg[idx], coord[pos]);
    }
    if (l == r) {
        return ans;
    }

    int mid = (l + r) >> 1;
    if (pos <= mid) {
        ans = min(ans, query_min(idx << 1, l, mid, pos));
    } else {
        ans = min(ans, query_min(idx << 1 | 1, mid + 1, r, pos));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> home_x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].r >> a[i].v;
    }

    sort(a + 1, a + n + 1, [](const Node &lhs, const Node &rhs) {
        if (lhs.x != rhs.x) {
            return lhs.x < rhs.x;
        }
        if (lhs.r != rhs.r) {
            return lhs.r < rhs.r;
        }
        return lhs.v < rhs.v;
    });

    coord_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || a[i].x != a[i - 1].x) {
            coord[++coord_cnt] = a[i].x;
        }
    }

    for (int i = 1; i < (MAXN << 2); i++) {
        seg[i].empty = true;
    }

    long double ans = INF;
    int i = 1;
    while (i <= n) {
        int j = i;
        while (j + 1 <= n && a[j + 1].x == a[i].x) {
            j++;
        }

        int pos = lower_bound(coord + 1, coord + coord_cnt + 1, a[i].x) - coord;

        for (int k = i; k <= j; k++) {
            if (k == 1) {
                // 第一个点就是移动公司本身，不需要接收费用，只需要启动费用。
                dp[k] = (long double) a[k].v;
            } else {
                long double best = INF;
                if (coord_cnt > 0 && !seg[1].empty) {
                    // 从所有左侧已建好的点里，找一个让当前点接收费用最小的。
                    best = min(best, query_min(1, 1, coord_cnt, pos));
                }
                if (best >= INF / 2) {
                    dp[k] = INF;
                } else {
                    dp[k] = best + (long double) a[k].v;
                }
            }

            if (dp[k] < INF / 2 && llabs(a[k].x - home_x) <= a[k].r) {
                ans = min(ans, dp[k]);
            }
        }

        for (int k = i; k <= j; k++) {
            if (dp[k] >= INF / 2) {
                continue;
            }
            Line line;
            // 若当前点 j 作为发送端，而后面某个点 i 要从它接收，
            // 额外费用是 sqrt((x_i - x_j)^2 / (4r_j)) = (x_i - x_j) / (2*sqrt(r_j))。
            // 所以转移可以写成：
            // dp[j] + v_i + x_i/(2*sqrt(r_j)) - x_j/(2*sqrt(r_j))
            // 对固定 j 来说，这就是一条关于 x_i 的直线。
            line.k = 1.0L / (2.0L * sqrtl((long double) a[k].r));
            line.b = dp[k] - line.k * (long double) a[k].x;
            line.empty = false;
            insert_line(1, 1, coord_cnt, line);
        }

        i = j + 1;
    }

    cout.setf(ios::fixed);
    cout << setprecision(3) << (double) ans << '\n';
    return 0;
}

复杂度

时间复杂度 O(nlogn)O(n log n)，空间复杂度 O(n)O(n)。

总结

这题表面是几何，核心其实是把几何费用公式整理成直线。

一旦写出：

  • 每个已建好的点 j 对应一条直线
  • 每个新点 i 只是在自己的 x_i 处查询最小值

Li Chao Tree 就是最自然的正解。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析