# 剪羊毛：题解

## 解法比较

出题人解法在起点、羊群与箱子之间预处理最短路，并让每群羊处于三种状态：未剪、保留全部羊毛、仅保留有益羊毛。转移可以直接去下一群羊，也可先绕箱子存掉增加耗时的羊毛；有益羊毛没有主动丢弃的必要，证明见下文。已剪集合只增不减，因此按新增羊群数逐层转移即可。

出题人实现每群用两位编码，给 $4^p$ 个编码准备指针，仅对可达的三状态组合分配 DP。Codex（GPT-6）采用的实现用三进制把这些组合连续编号，省去无效编码和分散分配。两者主要转移均为 $O(3^p p^2(c+1))$ ，加上关键点 BFS 等预处理；DP 本体为 $O(p3^p)$ 空间，两位编码的指针表另占 $O(4^p)$ .Codex 实现免去该表，完整复杂度见下文。三状态含义和箱子转移均来自出题人解法。

## 哪些羊毛需要保留

负效果羊毛只会降低移动耗时，没有背包容量限制，因此把它们的存箱时刻推迟到最后一次存箱，途中耗时不会增加。正效果羊毛则应在经过箱子时全部存入：提前卸下只会使以后更快，不会阻碍任何操作。零效果羊毛随任一类处理都不改变答案。

由此，每群羊只需三种状态：未剪毛；已剪毛且正效果羊毛已存箱；已剪毛且正效果羊毛仍携带。所有已剪羊群的负效果羊毛都一直携带到结束。无需按羊毛的具体份数枚举状态。

设 $N_i$ 为羊群 $i$ 的全部负效果之和，$P_i$ 为其全部正效果之和。若已剪集合为 $S$ ，仍携带正效果羊毛的羊群集合为 $C\subseteq S$ ，则步耗时为

$$v(S,C)=\max\left(1,t+\sum_{i\in S}N_i+\sum_{i\in C}P_i\right)$$

注意先求完整和，再与 $1$ 取最大值，不能每加入一份羊毛就截断一次。

## 压缩地图上的移动

从起点、每个羊群和每个箱子分别 BFS，求这些关键位置之间的最短步数 $d(u,v)$ .在两次改变背包状态之间，步耗时固定，所以沿最短步数路线行走即可。路过羊群或箱子可以不操作，不会破坏这个结论。

相邻两次剪毛之间只需考虑不经过箱子，或到一个箱子卸下所有正效果羊毛。卸下后背包在下一次剪毛前不再变化，访问更多箱子不会有收益，可用最短路替代。

## 三进制状态动态规划

定义 $dp[S,C,u]$ 为刚在羊群 $u$ 剪完毛后的最少总耗时。只保存这种操作后的状态，因此 $u\in C$ ；即使该群正效果总和为零，也保留这个状态标记。每个羊群三种状态，总数为 $3^p$ .

初始可以从起点直接去任一羊群 $u$ ，费用为 $t\,d(S_0,u)$ ，其中 $S_0$ 表示地图起点。设下一群为 $v\notin S$ ：

1. 直接前往：增加 $d(u,v)v(S,C)$ ，转到 $(S\cup\{v\},C\cup\{v\},v)$ .
2. 经箱子 $h$ 卸货：增加 $d(u,h)v(S,C)+d(h,v)v(S,\varnothing)$ ，转到 $(S\cup\{v\},\{v\},v)$ .

第二种枚举所有箱子。两种转移都严格增加已剪集合，所以按已剪集合的位掩码从小到大处理即可；不能直接按三进制状态编号递增，因为卸货会让某些三进制位变小。

所有羊群均已剪毛后，从当前位置走到任意箱子，把包括负效果在内的全部羊毛存入，取最小值。

## 正确性

前面的交换论证保证存在一个最优方案符合“负效果留到最后、正效果遇箱即卸”的规则。压缩移动后，该方案在每相邻两次剪毛之间必属于上述两种情况。动态规划枚举了所有剪毛次序及必要的存箱选择，转移费用与实际耗时一致，最后一步又保证全部羊毛入箱，因此所得答案正好是最优值。

## 复杂度与边界

令 $c$ 为箱子数，$V=ab$ .时间为 $O(pk+(p+c)V+3^p p^2c)$ ，空间为 $O(3^p p+(p+c)^2+V+pk)$ 的上界；实现流式读入羊群数量，不保存整个数量矩阵，还可省去 $pk$ 项。使用 64 位整数计算总耗时。

独立对拍在小地图上按“位置、已剪集合、具体携带羊毛集合”运行 Dijkstra，允许在箱子存任意子集，包括提前存负效果羊毛，从而验证状态压缩的正确性。样例还覆盖障碍绕路、耗时下限和部分存箱。

## 程序与复现

参考程序见 [std.cpp](std.cpp)。使用 C++17 编译后，可用 `tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径>` 生成输入和答案。固定种子与用例目的见 [生成计划](tests/plan.json)。性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。