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

· · 题解

首先容易得到一些性质：首先把所有打算用 AI 的一起放在所有手写前面不劣，且根据 exchange arugment 有 AI 之间是按照 B_i 升序排序的，所以其实只要觉得哪些任务用 AI，倒数第 k 个 AI 的代价是 kB_i。

然后就可以 DP 了，初始默然全手写，代价为 \sum A_i，按照 B_i 降序处理，设 f(k) 表示当前选了 k 个 AI，转移为 f'(k)=\min(f(k), f(k-1)+kB_i-A_i)。现在可以做到 \mathcal{O}(n^2)。

根据一些说法，不妨先假设这个东西是凸的。考察差分，d_k=f(k)-f(k-1)，那么 kB_i-A_i 更优等价于 d_k-kB_i>A_i，我们可以在后续归纳说明 d_{k+1}-d_{k}\ge B_i，所以 d_k-kB_i 单调不降，只需要找到第一个 d_k-kB_i 不降的位置，用二分和平衡树维护 d_i 即可做到 \mathcal{O}(n\log n)。

上面结论的证明：考虑归纳，由于 B_i 不降，若 d_{k+1}-d_k\ge B_{i-1}，我们自然有结论成立，于是只要证 d_{k+1}'-d_k'\ge B_i，由于 d' 相当于一个单点插入和后缀加，列一下有变化的地方就发现不会出现问题。

但是上面的东西看上去不太好想到，这个 d_{k+1}-d_k\ge B_i 是一个比凸性更强的性质，转移中比较不同的地方就是 kB_i 这一项，如果没有这一项，就是 f 和 [0,-A_i] 这个序列的闵可夫斯基和，显然是凸的。令 a=A_i,b=B_i，这个形式就是 f'(k)=\min(f(k),f(k-1)-a)。对于有 kb 的情况，我们考虑构造一个 g(k)=f(k)+h(k) 使得 g'(k)=\min(g(k),g(k-1)-a)。那么有 f'(k)=\min(f(k),f(k-1)+h(k-1)-h(k)-a)，于是我们要求 h(k-1)-h(k)=kb，那么 h(k)=-b\binom{k+1}2，所以其实 f 的二阶差分 \ge b 等价于 g 是凸的。当 b 减小时，g(k) 会加上凸函数 \binom{k+1}2 的正数倍，所以仍然是凸的。于是 f 的二阶差分始终 \ge b，或者你直接维护 g 的差分也是没问题的，每次转移是插入一个 -a。这里的思路是什么？kb 这一项比较讨厌，我们尝试通过一些转化把它变为常见的形式，进而说明凸性甚至一个更强的性质。思路来源：jiangly。