最优值没有留下回家的路

王城每年举行一次盲人厨师大赛。

厨师们把食材放在一条长桌上。评委允许把桌面切成若干段，每段选一个“代表食材”定价，再把各段得分相乘。

赛后公告只公布最高总分，冠军本人却拿不到自己的菜单。

地图官说：“分数已经在榜上。”

厨师说：“我晚上要按这份菜单回家。”

问题在于，评委每次比较两份菜单，只留下较大的分数。

小的那份连同它的食材、分割点、价格，一起被擦掉。第二轮比较又擦一遍。

王后要求补发一张路线图。厨房里没人知道，最高分那张菜单在两轮擦除里换过几次主人。

简化题面

┌─ [P3592] 洗车店
├─ 平台: 洛谷
├─ 题意: 在区间动态规划中求最优代价，并输出达到最优值的具体方案。
├─ 输入: 一段序列及其代价参数。
├─ 输出: 最优值与每个位置最终所属的方案信息。
├─ 数据范围: 区间长度与值域决定状态数量。
├─ 关键限制: 状态经过多层取最大或最小后，仍需恢复实际决策。
└─ 完整题面: https://www.luogu.com.cn/problem/P3592

数字还在，来路没了

P3592 的计算有两层选择。

固定区间最低价为第 k 档时，dp[l][r][k] 要在许多位置 p 中取最优。随后 best[l][r][k] 又在所有 k' >= k 的状态里取后缀最优。

求值时，一个数字足够。还原时，两轮 max 各自抹掉了一层身份。

ch[l][r][k]    best 从哪个实际价格档 kk 来
last[l][r][kk] dp 在该价格档选择哪个位置 p

这两张表对应两次选择。外层先决定价格档，内层再决定分裂位置。

先找价格，再找位置

从 best[1][n][k] 开始还原时，顺序必须和计算依赖相反：

int kk = ch[l][r][k];
int p  = last[l][r][kk];
answer[p] = price[kk];
trace(l, p - 1, kk);
trace(p + 1, r, kk);

直接读取 last[l][r][k] 会把外层后缀选择漏掉。last 在实际采用的 kk 状态里才有意义。

价格档确定以后，p 才是当前区间的真实分裂点。先找位置，等于拿另一张菜单上的刀工路线来切案板。

相等也需要证人

还有一个很小的等号：

if (candidate >= dp[state]) {
    dp[state] = candidate;
    last[state] = p;
}

只写 > 时，最优值仍可能正确。初值和候选同为 0，last 却一直没有合法位置。

也可以使用明确的未初始化哨兵，或在最后重新扫描转移寻找等式成立的决策。方法可以换，证据必须留下。

评委只发分数，厨师要菜单

动态规划若只要求最优值，状态可以把候选压成一个数。题目一旦要求方案、路径、构造或解释，每次压缩都要同时保留“这个数从谁那里来”。

值是结论。ch 和 last 是证书链。

链上任何一环缺席，分数仍能打印，菜单已经回不来了。

王后收到两张纸：一张写最高总分，一张写每次选择的来源。她把第二张交给厨师，第一张留在公告栏。

夜里，厨房的灯灭了。厨师沿着证书链切回家，案板上没有多出一刀。

发布信息草案

• 标题：最优值没有留下回家的路
• 摘要：多层最优化会逐层抹去决策来源，方案还原必须为每一层保留独立的来源记录。
• 标签：区间 DP、方案还原、决策记录、证书、路径恢复