题解：AT_abc400_g [ABC400G] Patisserie ABC 3

Austin0116 · 2026-07-21 19:47:41 · 题解

分析

首先我们发现，我们并不用关心是选哪些蛋糕，只关心哪些蛋糕对答案有贡献。所以我们可以考虑一个 DP，定义状态 f_{i,j,S} 表示考虑前 i 个蛋糕，选了 j 个蛋糕，当前 x，y，z 的奇偶性是 S 的最大价格总和，转移是容易的，时间复杂度 O(n^2)，考虑优化。

我们考虑 wqs 二分，通过二分时增加选物品的惩罚，使得最后恰好选了 k 个物品，这样子时间复杂度就是 O(n \log V)。需要根据二分的东西注意一些细节。