题解：P6715 [CCO 2018] Fun Palace

BPG_ning · 2025-10-16 17:23:07 · 题解

宇宙题，大道至简。

以下称题面中生物为人，称 当前 的第 i 个位置的人数为 c_i，当前 的定义需要结合语境。

发现操作可逆。

设 f_{i,j} 表示在 考虑全局 的情况下，c_i 能通过若干操作得到的最大值 =j，此时 \sum_{k=1}^{i} c_k 的最大值。

考虑转移从 f_{i,*}\to f_{i+1,*}，分类讨论：

当 j\geq a_i+b_i 时，此时 c_{i+1}=0（不然 c_i 可以更大），所以 c_{i+1} 的最大值也是 j，转移有 f_{i,j}\to f_{i+1,j}。

当 j\geq a_i 时，同理，c_{i+1}=0，但是你不能把所有 j 个人送过去了，转移有 f_{i,j}\to f_{i+1,j-a_i}。

为什么上面恰好是 j 和 j-a_i 呢？如果能大于他们，我们再将从 i\to i+1 的操作撤销，发现 c_{i+1}\ne 0，矛盾。

当 j<a_i 时，考虑 c_{i+1}。

当 c_{i+1}=b_i 时，c_{i+1} 可以把 j 全都抢走，有转移 f_{i,j}\to f_{i+1,j+b_{i}}+b_i。

当 c_{i+1}<b_i 时，c_{i+1} 什么都干不了，有转移 f_{i,j}\to f_{i+1,k}，其中 k<b_i。

当 c_{i+1}>b_i 时，显然 c_{i+1} 还能给 c_{i} 更多人，此时 c_{i} 不是最大，矛盾。所以不考虑其转移。

初始时有 \forall i\in[0,e),f_{1,i}=i，直接转移即可，时间复杂度 O(nV)，其中 V=\max(a_i,b_i,e)。