题解：P2975 [USACO10JAN] Taking Turns G

WZWZWZWY · 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（后手最优）就行了。