思路与算法

令B_i=Σb_j、W_i=Σj b_j，dp_i为前i个牧场且在i建站的最小费用。前站j的转移为a_i+iB_i-W_i+dp_j+W_j-iB_j，化为斜率-B_j、截距dp_j+W_j的直线在x=i处取最小。b_j>0使斜率严格递减，查询i递增，用双端凸包维护。

正确性说明

每个控制站负责从前站后一格到自身的连续区间，公式精确展开该段放养距离费用；所有站点分段与转移一一对应。最后牧场必须建站，否则它不受任何东边站控制，因此答案dp_n。单调斜率及查询允许删除永远不会再最优的直线和过期队首，保留最小值。

复杂度

读入、前缀初始化和每条线进出队各一次，共O(n)时间，O(n)空间；最坏交点叉乘使用128位。

易错点

线段费用包括站自身但距离为0。中间值如iB_i可达10^16量级，用64位；交点比较更大，用128位，避免浮点交点误差。不要擅自把本题当任意位置的非单调凸包。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct L {
    ll m, b;
};
__int128 val(L l, ll x) {
    return (__int128)l.m * x + l.b;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n + 1), B(n + 1), W(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        ll b;
        cin >> b;
        B[i] = B[i - 1] + b;
        W[i] = W[i - 1] + b * i;
    }
    deque<L> h;
    h.push_back({0, 0});
    ll dp = 0;
    for (int i = 1; i <= n; i++) {
        while (h.size() > 1 && val(h[0], i) >= val(h[1], i))
            h.pop_front();
        dp = a[i] + i * B[i] - W[i] + (ll)val(h.front(), i);
        L z{-B[i], dp + W[i]};
        while (h.size() > 1) {
            L x = h[h.size() - 2], y = h.back();
            if ((__int128)(y.b - x.b) * (y.m - z.m) >= (__int128)(z.b - y.b) * (x.m - y.m))
                h.pop_back();
            else
                break;
        }
        h.push_back(z);
    }
    cout << dp << '\n';
}