题解：P17546 [JAG 2026 Summer Camp #2] Vibe Coding

· · 题解

来点观察。

首先就是发现如果你知道哪些用 A，哪些用 B，就一定能确定顺序，肯定是先做 B 的部分，按照 B 升序做，然后随便做 A。

然后按照 B 降序排，就可以轻松写背包：f_{i,j} = \min(f_{i-1,j-1}+B_i\times j - A_i, f_{i-1,j})。

然后看上去很不可优化。考虑从差分上思考。

打表，发现差分数组是单调递减的。然后从表中猜测 f 是凸的。这样就可以维护差分数组了。

既然差分数组是单调的，那么就可以找到第一个满足 d_{i-1,j} > B_i\times j - A_i 的点 k，然后发现新的差分数组是这样的：

d_i = \{d_{i-1,1},\cdots,d_{i-1,k-1},kB_i-A_i,d_{i-1,k}+B_i,\cdots, d_{i-1,i-1}+B_i\}

然后就直接用平衡树维护差分即可。做到 O(N\log N)。

至于证明，留给读者自行推导。

Tips：需要得到比凸的更强的性质才能证明上述维护差分过程成立，性质是 d_{k,i}-d_{k-i-1} \ge B_{k+1}。