题解：P10041 [CCPC 2023 北京市赛] 史莱姆工厂
E.Space
·
·
题解
考虑最后一次卖的那个史莱姆是由最初的哪些史莱姆合并成的。
这些史莱姆是原序列的一个子序列。它们需要满足哪些性质呢？
首先肯定必须同色。然后考虑最后一次合并之前的情况。
- 如果没有最后一次合并，也就是说，这个子序列只包含一个史莱姆，那么一定可行。这时需要增加 k-m_i 次质量，这次卖出可以获得 p_k-(k-m_i)w 的收益。
- 如果存在最后一次合并，由于任何时刻史莱姆的质量不能大于等于 k，否则会被立即卖掉，所以合并之前的两个史莱姆的质量必须均小于 k。也就是说，这个子序列必须能够分成前后两段，使得每一段的质量和均小于 k。由于题目保证了 p_i-w<p_{i-1}，所以如果需要增加质量，一定存在一种最优解是在最后一次合并之后再开始增加质量。所以，如果整个子序列的质量总和仍小于 k，那么卖出收益是 p_k-(k-sum)w，否则是 p_{sum}。为方便起见，对 1\le i <k 定义 p_i=p_k-(k-i)w。
这时，原序列被这个子序列分割成了若干极长连续段，每个极长连续段都不包含子序列中的史莱姆。由于选中的子序列是最后被卖掉的，所以这些被分割出来的连续段之间一定互不干扰，也就是说，在任何连续段之内的操作都不会影响到其他连续段的状态。于是就可以区间 DP 了。
然后，为了保证最后一次卖出的史莱姆恰好是选中的子序列，需要保证分割出来的连续段中最后一次卖出的史莱姆的颜色不能与连续段之外两侧的颜色相同，否则就会发生合并。
于是就可以设计状态和转移了。
记 f(l,r) 为区间 [l,r] 的答案。
记 g_1(l,r,s_1) 为，在区间 [l,r] 中选了一个子序列，满足 r 属于子序列，且属于子序列中两个质量和 <k 的段的前面一段，且此时前面一段的质量和为 s_1 时，区间 [l,r] 内所有被分割出的极长连续段的答案之和的最大值。
记 g_2(l,r,s_1,s_2) 为，在区间 [l,r] 中选了一个子序列，满足 r 属于子序列，且属于子序列中两个质量和 <k 的段的后面一段，且此时前面一段的质量和为 s_1，后面一段的质量和为 s_2 时，区间 [l,r] 内所有被分割出的极长连续段的答案之和的最大值。
$g_1$ 的转移分两种情况，子序列长度为 $1$ 和子序列长度大于 $1$。子序列长度为 $1$ 说明 $r$ 是子序列中唯一的位置。所以有 $g_1(l,r,m_r)\xleftarrow{\max}f(l,r-1)$。注意此时 $s_1$ 必须等于 $m_r$。子序列长度大于 $1$ 时考虑枚举子序列中倒数第二个位置 $i$。这时有 $g_1(l,r,s_1)\xleftarrow{\max}g_1(l,i,s_1-m_r)+f(i+1,r-1)$。
$g_2$ 的转移分两种情况，子序列的两个质量和不超过 $k$ 的段中的第二段的长度为 $1$ 和长度大于 $1$。两种情况均考虑枚举子序列中倒数第二只史莱姆的位置 $i$。长度为 $1$ 说明 $r$ 是第二段中唯一的位置。所以有 $g_2(l,r,s_1,m_r)\xleftarrow{\max}g_1(l,i,s_1)+f(i+1,r-1)$。注意此时 $s_2$ 必须等于 $m_r$。第二段长度大于 $1$ 时有 $g_2(l,r,s_1,s_2)\xleftarrow{\max}g_2(l,i,s_1,s_2-m_r)+f(i+1,r-1)$。
然后就做完了。答案是 $f(1,n)$。
$f$ 一共有 $O(n^2)$ 种状态，单次转移需要枚举 $i,s_1,s_2$，所以单次转移复杂度是 $O(nk^2)$，总复杂度是 $O(n^3k^2)$。
$g_1$ 一共有 $O(n^2k)$ 种状态，单次转移需要枚举 $i$，所以单次转移复杂度是 $O(n)$，总复杂度是 $O(n^3k)$。
$g_2$ 一共有 $O(n^2k^2)$ 种状态，单次转移需要枚举 $i$，所以单次转移复杂度是 $O(n)$，总复杂度是 $O(n^3k^2)$。
所以该算法总时间复杂度为 $O(n^3k^2)$，空间复杂度为 $O(n^2k^2)$。