状态坐标从代价里长出来

暴雨把市立博物馆的屋顶打出了三个洞。

闭馆通知贴在门上，撤展通知贴在通知上。地下库房里，一串待搬走的画还连在传送带上。

搬运工每次取走当前连着的一段，装进木箱，封箱以后才结算保险费。

出纳的算法很古怪。他只看箱里最贵的画和最便宜的画，价差越大，账单越难看。

箱子里有多少幅，画挂在第几号钉子上，他都不问。

学徒画了一张路线图。

红笔圈出最贵的画。蓝笔圈出最便宜的画。

每一段传送带都标上两个位置，像给一场谋杀案找脚印。

出纳拿来两张旧保单。两张图上的红蓝脚印完全一样，金额却差了十倍。

屋顶又漏下一滴水。正好落在学徒的红笔上。

他把路线图折起来，改问出纳：“你结账时，手指落在哪个数字上？”

出纳指了指价差。没有指钉子。

撤展继续。学徒把可能留到最后一箱的画，按估值圈成一个范围。

范围外的画先装走，遇到一段就结一段；范围里的画暂时留着，像一群拒绝离场的演员。

这一回，传送带上的顺序终于帮上了忙。它决定谁先被搬走，估值范围决定出纳最后会收多少钱。

多年以后，博物馆的培训手册只留下一个提醒：先问账单会读取什么，再决定地图画在哪一张纸上。

简化题面

┌─ [P5336] 成绩单
├─ 平台: 洛谷
├─ 题意: 反复删除当前序列中的连续段，每次按该段极值支付费用，求最小总代价。
├─ 单次费用: A + B * (max - min)^2。
├─ 输入: n、A、B，以及按顺序排列的 n 个分数。
├─ 输出: 发完全部成绩单的最小总代价。
├─ 数据范围: n <= 50，状态维度多，需要压缩无效值域。
├─ 关键限制: 一批的费用只读取该批最小值与最大值。
└─ 完整题面: https://www.luogu.com.cn/problem/P5336

先看出纳的手指

取一段具体序列：

30 50 40 10 20 40

最贵和最便宜的画站在哪里，决定不了 (max-min)^2 的数值。把两个估值换掉，脚印可以原样保留，账单照样翻倍。

区间位置负责描述搬运顺序。费用读取的是值域端点。

两种信息都可能进入状态，职责各自分开。

设最后一箱保留的估值范围是 [x,y]。对原序列区间 [l,r]，定义：

f[l][r][x][y]
= 先发掉值域 [x,y] 之外的成绩单，留下区间内成绩单的最小代价

g[l][r]
= 发完 [l,r] 的最小总代价

最后一箱封口时，再付这一笔：

g[l][r] = min(f[l][r][x][y] + A + B * (y-x)^2)

值域内的成绩单形成隔板。左端成绩单落在范围内，就留到最后；落在范围外，就先找一个结束点 k，把 [l,k] 这箱结清，再处理右边。

if (x <= a[l] && a[l] <= y) {
    f[l][r][x][y] = f[l + 1][r][x][y];
} else {
    for (int k = l; k < r; ++k) {
        f[l][r][x][y] = min(f[l][r][x][y],
                            g[l][k] + f[k + 1][r][x][y]);
    }
}

k 是搬运工停下来的位置。[x,y] 已经决定 a[l] 的去留，端点剥离的分支因此可以写成一条明确的 if。

三套坐标不要共用一支笔

值域端点只取原序列出现过的分数。最后一箱非空，最高分和最低分总会来自真实成绩单，空档没有资格当端点。

离散化以后，代码里同时存在三种整数：

l,r        原序列位置
i,j        值域端点的 rank，用作数组下标
w[i],w[j]  真实分数，用来判断归属、计算费用

把真实分数塞进 f 的下标，数组立刻越界。循环采用 0-based，最后却读取 g[1][n]，屏幕上会出现 0x3f3f3f3f。

模型已经正确，坐标仍然会在代码里冒名顶替。

变量名写长一点。leftPos、lowRank、lowValue。

少猜一次，通常比少敲几个字符划算。

空区间的代价是 0。单个成绩单若被留在最后一箱，极值相同，平方项归零，只支付固定费 A。

博物馆终于断电。出纳收走最后一张保单，红笔和蓝笔都留在桌面上。

他结账时，仍然只看价差。路线图安静地指向传送带，没有人再拿它去算保险费。

发布信息草案

• 标题：状态坐标从代价里长出来
• 摘要：区间 DP 的状态轴应覆盖未来代价会读取的信息，位置、离散 rank 与真实分值各有自己的职责。
• 标签：区间 DP、状态设计、值域、离散化、成绩单