自动搬运

查看原文

来自洛谷，原作者为

	WZWZWZWY 一只蜷缩在只因房里敲代码的蒟蒻（真）|| ╯ω╰ || 这只蒟蒻已经被滚去学whk了qwq

搬运于2025-08-24 21:44:00，当前版本为作者最后更新于2024-09-13 21:47:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好题！有点像博弈论的 DP。

题目描述

两头奶牛 Bessi 和 Dessie 走过一条路吃草，共 $n(1\le n \le 7\times 10 ^ 5)$ 个格子，第 $i$ 个格子有重量为 $W_i(1 \le W_i \le 2 \times 10 ^{9})$ 的草，两牛轮流走，一旦某头牛走过了一格，那么这格的草再也不可能被任一头奶牛吃，每格的草只能被吃一次，所以两头牛只能往后走。Bessi 先走，每头牛每次都往最终自己能吃到最多草的格子走（若有多个格子则选择第一个能吃到最多草的格子），他们都知道对方也想吃到最多的草，问最后 Bessi 和 Dessie 各吃到的草的重量。

思路

其他题解的状态定义似乎没表述清楚。

用 $f_i$ 表示到了现在这头牛吃（先手），吃 $i$ 及以后的草堆所能获得的最大价值。

用 $g_i$ 表示下头牛吃（后手），吃 $i$ 及以后的草堆所能获得的最大价值。

假设现在该 $A$ 牛吃（先手），$A$ 吃完后，此时 $B$ 成了先手，$A$ 成了后手。$B$ 吃完后 $A$ 又成为先手……一头牛的先后手是交替的。

草堆从 $n$ 循环到 $1$，初始 $f_{n+1}=g_{n+1}=0$。

先手先选（废话），先手肯定选择 $f_{i+1}$ 和 $g_{i+1}+w_i$ 中最大的（即不选或者选择草堆 $i$）。

• 如果不选 $i$，那么就相当于没操作，$f_i=f_{i+1}$，$g_i=g_{i+1}$。

• 如果选择 $i$，此时先手和后手互换，$f_i=g_{i+1}+w_i$，$g_i=f_{i+1}$。

最后输出 $f_1$（先手最优）和 $g_1$（后手最优）就行了。