题解：P6715 [CCO 2018] Fun Palace

宇宙题，大道至简。

以下称题面中生物为人，称 当前 的第 $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)$。