思路与算法

F(l,r)表示彻底删除区间的最小代价。另设G(l,r,mn,mx)：左边已有一个待发批次，其分数范围为mn到mx，接下来还可从区间继续选同批元素的最小总代价。可以立刻结束该批，付批次代价再做F(l,r)；也可以选下一同批位置k，先付F(l,k-1)删去间隔，再把w_k并入范围，继续G(k+1,r,新mn,新mx)。F从第一元素作为待发批次开始。

正确性说明

任意方案中，包含区间首元素的那一批在最终发放前，其同批相邻保留元素之间的间隔必须已被独立删除。依次枚举这些保留元素正好对应G的第二种转移；其余尾部可在该批后独立删除，对应第一种。反向按转移顺序执行也都是合法连续段删除，因此完整且无非法方案。

复杂度

分数离散秩不超过n，F有O(n²)状态，G有O(n⁴)状态，每状态枚举O(n)下一位置，总O(n⁵)时间上界、O(n⁴)空间；表初始化O(n⁴)。n≤50时本实现使用整数稠密表。

易错点

分数离散只用于下标，范围平方必须使用原分数差。待发批次成本只付一次。a或b可为0，最优代价也可为0；不能因为输出措辞“正整数”就擅自禁止零成本输入。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int n, A, B;
vector<int> w, score, F, G;
int solve(int, int);
int open(int l, int r, int mn, int mx) {
    if (l > r)
        return A + B * (score[mx] - score[mn]) * (score[mx] - score[mn]);
    int &z = G[((l * n + r) * n + mn) * n + mx];
    if (z != -1)
        return z;
    z = A + B * (score[mx] - score[mn]) * (score[mx] - score[mn]) + solve(l, r);
    for (int k = l; k <= r; k++)
        z = min(z, solve(l, k - 1) + open(k + 1, r, min(mn, w[k]), max(mx, w[k])));
    return z;
}
int solve(int l, int r) {
    if (l > r)
        return 0;
    int &z = F[l * n + r];
    if (z != -1)
        return z;
    return z = open(l + 1, r, w[l], w[l]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> A >> B;
    w.resize(n);
    for (int &x : w)
        cin >> x;
    score = w;
    sort(score.begin(), score.end());
    score.erase(unique(score.begin(), score.end()), score.end());
    for (int &x : w)
        x = lower_bound(score.begin(), score.end(), x) - score.begin();
    F.assign(n * n, -1);
    G.assign(n * n * n * n, -1);
    cout << solve(0, n - 1) << '\n';
}