剪羊毛：题解¶
解法比较¶
出题人解法在起点、羊群与箱子之间预处理最短路，并让每群羊处于三种状态：未剪、保留全部羊毛、仅保留有益羊毛。转移可以直接去下一群羊，也可先绕箱子存掉增加耗时的羊毛；有益羊毛没有主动丢弃的必要，证明见下文。已剪集合只增不减，因此按新增羊群数逐层转移即可。
出题人实现每群用两位编码，给 \(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\) ，则步耗时为
注意先求完整和，再与 \(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\) ：
- 直接前往：增加 \(d(u,v)v(S,C)\) ，转到 \((S\cup\{v\},C\cup\{v\},v)\) .
- 经箱子 \(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。使用 C++17 编译后，可用 tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径> 生成输入和答案。固定种子与用例目的见 生成计划。性能测量见 评测环境与性能。