CF1342F Make It Ascending

题意

给予一个包含\(n\)个元素的数组\(a\)，你可以进行以下操作：

• 选择两个不同的元素\(a_i,a_j\)（\(1 \le i,j \le n\)，\(i \ne j\)）
• 将\(a_j\)的值加上\(a_i\)，并移除\(a\)中的第\(i\)个元素。

求使\(a\)数组严格递增（对于\(1 \le i < n\)，有\(a_i<a_{i+1}\)）所需的最少操作数（可以为\(0\)）。

题解

首先对于这道题我们容易想到状压。
但是直接状压没有太好的方法，考虑到最后的样子一定是原数列的若干个集合并在不同的数字上。
这些数字的值和位置都

容易想到一个朴素的 \(dp\)。
\(f_{S,p,v}\) 表示使用了 \(S\) 这个点集，目前的代表原位置在 \(p\)，值为 \(v\) 的最小合并次数。
但是这样很难，因为 \(v\) 这一维的大小是值域，这东西是很大的，不太行。

注意到一个事情，对于 \(f_{S,p,v}\) 和 \(f_{S,p,v'}\) 来说，若 \(v<v'\) 且 \(f_{S,p,v} \leq f_{S,p,v'}\) 则后者显然无用。
这个东西就有一个类似于单调性的东西，对于所有 \(f_{S,p,v}\) 若前两维相同，且值相同，则只有最小 \(v\) 状态有用。

注意到答案可能不会很大，同时有前面的性质，所以考虑交换维护的值域和答案。

\(f_{S,i,p}\) 表示 使用了的点集为 \(S\) ，目前在处理的是第 \(i\) 个集合，代表元位置为 \(p\)，最后一个集合的值的最小值。
转移的话就枚举一个集合看一下能否单调即可，最后的状态中显然就是找 \(i\) 最大且可以到达的状态。
输出路径记录一下就好了。