题解

思路

先把相邻且同色的夹克压缩成一个连续段。记压缩后共有 $m$ 段，第 $i$ 段颜色为 $u_i$、长度为 $s_i$，移动整段的代价为 $w_i=s_iY$。

最优方案中，打包时总会取走栈顶极长同色段；移动时也只需考虑移动完整连续段。若只移动某段的一部分，则两栈顶部会同时出现同色夹克，直接打包原栈顶不会更差。

定义 $dp[l][r]$ 为只处理连续段 $l\ldots r$ 的最小代价。可以直接用 $X$ 打包第 $l$ 段，再处理 $[l+1,r]$；也可以把第 $l$ 段与后面若干个同色段合并打包。被选同色段之间的区间都是独立子问题。

对固定的 $l$，只看满足 $u_j=u_l$ 的位置。维护：

• $F_j$：把从 $l$ 到 $j$ 选中的同色段按第一种移动方向合并时的最小代价；
• $G_j$：按另一种移动方向合并时的最小代价。

初值为 $F_l=2w_l$、$G_l=w_l$。若上一个选中位置是 $k$，则

选到 $j$ 后，合并这些段并打成一包的代价为

与直接打包第 $l$ 段的方案取最小即可。

做法

子任务 1 可把“左栈、右栈”的完整状态作为最短路节点，枚举两次移动和两次打包操作，用 Dijkstra 求空状态的最短距离。

若 $X\le Y$，移动一件夹克的代价已经不小于直接打包一个栈顶连续段，任何合并节省的打包次数都不足以抵消移动代价，因此答案就是压缩后连续段数乘 $X$。

子任务 3 对每个区间 $[l,r]$ 重新计算上述 $F,G$，复杂度为 $O(m^4)$。

满分算法按 $l$ 从大到小预先计算所有同色位置间的 $F,G$，再枚举右端点更新 $dp[l][r]$，把重复计算消除到 $O(m^3)$。

复杂度

• 子任务 1 的状态数为指数级，适用于 $N\le9$。
• 子任务 2 的时间复杂度为 $O(N)$，空间复杂度为 $O(1)$（不计输入）。
• 子任务 3 的时间复杂度为 $O(N^4)$，空间复杂度为 $O(N^2)$。
• 满分算法的时间复杂度为 $O(N^3)$，空间复杂度为 $O(N^2)$。