这是官方题解的 AI 中文翻译。

首先，我们注意到两个有用的事实：

• 最大化所取元素之和，等价于最大化你与对手所取元素之差。
• 只要桌上还剩至少一块，两个人已经吃掉的总量总是相同，因此此时双方的差值为 $0$。

为了解决本题，我们可以采用 $O(n^2 \cdot \max\limits_i(w_i))$ 的动态规划：

设 $dp[l][r][dif]$ 表示当前在区间 $[l, r]$ 上进行游戏，且当前你比对手晚 $dif$ 秒开始吃（$dif$ 可以为负），此时你与对手所取总量的差值。

动态规划的初始状态为：$dp[i][i-1][dif] = 0$，最终答案为 $dp[0][n-1][0]$。

$dif$ 的正负决定了当前由谁来选择先取哪一块。转移方式如下：

• 当 $dif \leq 0$ 时：

$$dp[l][r][dif] = \max \left\{dp[l + 1][r][dif + w[l]] + w[l],\ dp[l][r - 1][dif + w[r]] + w[r]\right\}$$

• 当 $dif > 0$ 时：

$$dp[l][r][dif] = \min \left\{dp[l + 1][r][dif - w[l]] - w[l],\ dp[l][r - 1][dif - w[r]] - w[r] \right\}$$

在这个动态规划中，$|dif| \leq \max\limits_i(w_i)$，因此状态总数为 $O(n^2 \cdot \max\limits_i(w_i))$，每个状态有两种转移。

对于满足 $w_{i+1} \leq 2 \cdot w_i$ 的子任务，我们证明如下性质：在这样的限制下，对于任意可达状态 $(l, r, dif)$，都有 $|dif| \leq w_{r+1}$（特例：若 $r = n - 1$，则 $|dif| \leq w_{n-2}$）。

证明思路如下：在任意一次转移中，$dif$ 总是向 $0$ 靠近，因此其绝对值要么减少，要么不会超过最后取走的那块 $w_i$。因此，对于 $[l, r] \to [l+1, r]$ 的转移，关系始终成立；对于 $[l, r] \to [l, r-1]$ 的转移，由于 $w_{r+1} \leq 2 \cdot w_r$，关系同样成立。

由此可知，对于每个 $l$，可达的 $(r, dif)$ 对不超过 $O(\sum\limits_{i=0}^{n-1} w_i) = O(W)$，总状态数为 $O(n \cdot W)$，每个状态仍有两种转移。

接下来，为了解决完整问题，我们需要调整动态规划的转移方式，使其始终满足 $|dif| \leq w_{r+1}$。

具体来说，如果某个人在轮到对手之前连续取了多块，他总可以先取小的再取大的。因此，我们保留 $[l, r] \to [l+1, r]$ 的转移（该转移保持不变量），而对于 $[l, r] \to [l, r-1]$，我们用 $[l, r, dif] \to [l, r', dif']$ 替代，表示当前玩家连续取最大的若干块，直到轮到对手或游戏结束。

这些转移同样保证 $|dif| \leq w_{r+1}$，因此总状态数为 $O(n \cdot W)$，每个状态有两种转移。

还需注意，$r'$ 的取值仅与 $r$ 和 $dif$ 有关，与 $l$ 无关，因此可以在 $O(W \cdot \log n)$ 的时间内预处理。

最终算法的总复杂度为 $O(n \cdot W)$，足以通过所有测试点。