题解：拱桥建造最小花费（动态规划+凸包优化+双指针）

一、题目核心分析

1. 问题建模

• 柱子必须建在给定关键点上，且首尾必建，相邻柱子间为半圆形拱门。
• 花费由两部分组成：柱子花费（$\alpha \times$ 柱子总高度）+ 拱花费（$\beta \times$ 相邻间距平方和）。
• 核心约束：半圆拱门不能低于地面，即相邻柱子 $i$ 和 $j$ 满足 $h - \frac{x_j - x_i}{2} \geq \max_{k=i}^j y_k$（半圆最低点不低于区间地面最高海拔）。

2. 动态规划转化

• 定义 $dp[k]$：以第 $k$ 个关键点为最后一根柱子的最小花费。
• 状态转移：$dp[k] = \alpha \cdot (h - y_k) + \min_{i \in [left, k-1]} \left\{ dp[i] + \beta \cdot (x_k - x_i)^2 \right\}$，其中 $[left, k-1]$ 是满足约束的合法前驱区间。
• 初始状态：$dp[1] = \alpha \cdot (h - y_1)$（仅第一根柱子的花费）。

二、关键优化策略

1. 双指针确定合法前驱区间

• 性质：对于固定 $k$，合法前驱 $i$ 是连续后缀（$left \leq i < k$），且 $left$ 随 $k$ 单调递增（因 $x_k$ 增大，约束更严格）。
• 用单调队列维护区间 $[left, k]$ 的最大 $y$ 值，快速验证约束。

2. 凸包优化状态转移

• 状态转移中的最小值项可变形：$$dp[i] + \beta \cdot (x_k - x_i)^2 = \beta x_k^2 + (dp[i] + \beta x_i^2) - 2\beta x_k x_i $$
• 令 $a[i] = x[i]$，$b[i] = dp[i] + \beta x_i^2$，则需最小化 $b[i] - 2\beta x_k \cdot a[i]$（$\beta x_k^2$ 为常数，可忽略）。
• 该式等价于平面点 $(a[i], b[i])$ 与斜率 $m=2\beta x_k$ 的直线截距最小值，利用凸包+单调队列优化（$a[i]$ 和 $m$ 均单调递增）。

三、完整算法步骤

1. 输入读取与初始化：读取关键点坐标和参数，初始化 $dp$ 数组和单调队列。
2. 双指针维护合法区间：对每个 $k$，调整 $left$ 确保前驱 $i$ 满足约束，用单调队列维护区间最大 $y$ 值。
3. 凸包优化转移：
   • 将合法前驱 $i$ 作为平面点加入凸包（单调队列维护凸性）。
   • 按当前斜率 $m=2\beta x_k$ 从凸包中快速找到最优前驱 $i$。
4. 计算结果：最终 $dp[n]$ 为答案，若为无穷大则输出 impossible。

四、C++ 代码实现

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

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

    int n, h, alpha, beta;
    cin >> n >> h >> alpha >> beta;

    vector<ll> x(n + 1), y(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
    }

    vector<ll> dp(n + 1, INF);
    dp[1] = 1LL * alpha * (h - y[1]);

    deque<int> mq_max;   // 维护滑动窗口最大值（y）
    deque<int> mq_convex;// 维护凸包上的点（索引）
    mq_max.push_back(1);
    mq_convex.push_back(1);

    int left = 1;
    for (int k = 2; k <= n; ++k) {
        // 维护单调队列：保证队首是当前窗口最大y的索引
        while (!mq_max.empty() && y[k] >= y[mq_max.back()]) {
            mq_max.pop_back();
        }
        mq_max.push_back(k);

        // 调整left，确保[left, k]满足约束：2h - (x[k]-x[left]) >= 2*max_y
        while (left < k) {
            int current_max_y = y[mq_max.front()];
            if (2LL * h - (x[k] - x[left]) >= 2LL * current_max_y) {
                break;
            }
            // 移动left，移除窗口外的元素
            if (mq_max.front() == left) {
                mq_max.pop_front();
            }
            left++;
        }

        if (left >= k) {
            dp[k] = INF;
            continue;
        }

        // 将k-1加入凸包（若dp[k-1]合法）
        if (k - 1 >= 1 && dp[k - 1] != INF) {
            ll a_k1 = x[k - 1];
            ll b_k1 = dp[k - 1] + 1LL * beta * a_k1 * a_k1;
            // 维护凸包的下凸性
            while (mq_convex.size() >= 2) {
                int j = mq_convex[mq_convex.size() - 2];
                int l = mq_convex[mq_convex.size() - 1];
                ll a_j = x[j], b_j = dp[j] + 1LL * beta * a_j * a_j;
                ll a_l = x[l], b_l = dp[l] + 1LL * beta * a_l * a_l;
                // 斜率比较：(b_l - b_j)/(a_l - a_j) >= (b_k1 - b_l)/(a_k1 - a_l)
                ll s1 = (b_l - b_j) * (a_k1 - a_l);
                ll s2 = (b_k1 - b_l) * (a_l - a_j);
                if (s1 >= s2) {
                    mq_convex.pop_back();
                } else {
                    break;
                }
            }
            mq_convex.push_back(k - 1);
        }

        // 移除凸包中不在[left, k-1]的点
        while (!mq_convex.empty() && mq_convex.front() < left) {
            mq_convex.pop_front();
        }

        if (mq_convex.empty()) {
            dp[k] = INF;
            continue;
        }

        // 找到当前最优的前驱i
        while (mq_convex.size() >= 2) {
            int i = mq_convex[0];
            int j = mq_convex[1];
            ll a_i = x[i], b_i = dp[i] + 1LL * beta * a_i * a_i;
            ll a_j = x[j], b_j = dp[j] + 1LL * beta * a_j * a_j;
            ll m = 2LL * beta * x[k];
            // 比较j是否比i更优：b_j - m*a_j < b_i - m*a_i
            if ((b_j - b_i) < m * (a_j - a_i)) {
                mq_convex.pop_front();
            } else {
                break;
            }
        }

        int best_i = mq_convex.front();
        ll cost = dp[best_i] + 1LL * beta * (x[k] - x[best_i]) * (x[k] - x[best_i]);
        dp[k] = 1LL * alpha * (h - y[k]) + cost;
    }

    if (dp[n] == INF) {
        cout << "impossible\n";
    } else {
        cout << dp[n] << "\n";
    }

    return 0;
}

五、代码解释

1. 单调队列维护区间最大值：mq_max 保证队首是当前窗口 $[left, k]$ 的最大 $y$ 值，支持快速约束验证。
2. 凸包维护与查询：mq_convex 维护平面点 $(a[i], b[i])$ 的下凸包，利用单调递增的斜率和横坐标，实现 $O(1)$ 最优前驱查询。
3. 双指针优化：left 单调递增，确保每个点仅被访问一次，降低时间复杂度。

六、时间复杂度与空间复杂度

• 时间复杂度：$O(n)$（每个点入队、出队各一次，双指针线性移动）。
• 空间复杂度：$O(n)$（存储 $dp$ 数组和两个单调队列）。

该算法高效处理了 $n \leq 10^4$ 的数据规模，同时满足约束条件和最小花费的计算需求。