[THUPC2021 初赛] 切切糕

个人思路：

从小往大切，感性理解一下。

由于每个人都足够聪明，博弈 dp 只有后效型而没有前效性，所以从固定的最终状态倒序往前 dp，得到初始状态的答案。

状态：\(dp_{i,j}\) 表示还剩 \(i\) 个切糕，对手还有 \(j\) 次选择权时对手最多的切糕。

因为选择权在对手，自己的切糕不是很好维护，维护对手的切糕也是一样的。

转移：\(dp_{i,j} = \max{dp_{i-1,j} + size_{big}, dp_{i-1,j-1} + size_{small}}\)。

显然，对手可以用或者不用选择权。如果用，拿走大块。不用，拿走小块。

每块的大小决定权在我们手里。显然，对手选和不选的收益和固定，我们希望这两个值中的较大值最小，那么我们切糕的时候就要让二者收益尽可能平均。

具体而言：

如果 \(dp_{i-1,j-1} > dp_{i-1,j}\)，我们直接均分。

如果 \(dp_{i-1,j-1} + a_i < dp_{i-1,j}\)，我们不切（即分为大小为 \(0\) 和 \(a_i\) 的两块）。

否则，一定存在切法使二者相等。

答案即为 \(\sum\limits_{i=1}^n a_i - dp_{n,m}\)。

巴特西