题解：AT_keyence2021_e Greedy Ant

Easy_du · 2026-08-08 16:01:05 · 题解

\text{Description}

共 n 个糖果，给出每个糖果的美味值，还有一只蚂蚁，初始时在两个糖果中间，你与蚂蚁轮流行动，你先行动。

在你行动时，你可以选择任意一个糖果取走，并获得这个糖果的美味值。

在蚂蚁行动时，蚂蚁会选择与他相邻的两个糖果的美味值最大的糖果，获得这个糖果的美味值。

求你最大能获得多少美味值。

\text{Solution}

蚂蚁的每次行动的操作是固定的，所以最终答案只受我们的影响。

因为贪心策略基本不可行，所以考虑 dp。

我们不难发现，蚂蚁只可能取到附近四个糖果，如何取到呢？设这些糖果从左到右依次为 a, b, c, d，蚂蚁在 b, c 之间，如果我们把 b 取走了，就能取到 a 了，c 同理，可以依据这些情况进行转移。

我们发现 dp 的定义无从下手，分析题目后，我们考虑区间 DP，设 f_{l, r} 表示已经取了 l, r 的糖果，此时我们发现，如果我们取的糖果 x 并不是蚂蚁附近的糖果，那么只能可以考虑直接让蚂蚁去行动，我们等至 x 成为蚂蚁附近的糖果再取。

这种操作对答案没有影响，因为我们的这次操作如果这么选择就固定了，那么只需要在该操作即将影响蚂蚁时进行操作就不会影响答案。

我们又发现这种方式很难设计 dp，那么我们可以改为存储一次操作，这等价于没有将蚂蚁附近的糖果选择去选择其他糖果。

那么我们可以再依据新的想法设 f_{l, r, k} 表示已经取了 l, r 的糖果，还存储了 k 次操作时，能获得的最大美味值。

接下来依据 dp 状态，再结合蚂蚁只可能取到附近四个糖果结论设计转移：

下文中 a_{i} 指糖果 i 的美味值。

• 若我们选择了与蚂蚁相邻的糖果，分别考虑取蚂蚁左侧和右侧：

  • 如果我们选择取左侧且蚂蚁左侧不为空，我们消耗存储的一次操作进行转移：f_{l, r, k} = \max(f_{l, r, k}, f_{l - 1, r, k - 1} + a_{l})。
  • 如果我们选择取右侧且蚂蚁右侧不为空，我们消耗存储的一次操作进行转移：f_{l, r, k} = \max(f_{l, r, k}, f_{l, r + 1, k - 1} + a_{r})。
• 若我们不选择相邻的糖果，那么存储一步，判断蚂蚁选择左侧还是右侧。
  • 若为左侧，那么转移到左侧：f_{l, r, k} = \max(f_{l, r, k}, f_{l - 1, r, k + 1})。
  • 否则转移到右侧：f_{l, r, k} = \max(f_{l, r, k}, f_{l, r + 1, k + 1})。

区间 DP 枚举区间大小 len，左端点 l，右端点 r 以及存储操作 k，注意到转移依赖更大的区间，所以 len 的遍历顺序为 n - 1 \sim 0，l 正常从 0 开始，r 同样 l + len \sim n，k 一共可能存储 len + 1 次答案，故 0 \sim len + 1。

时空复杂度 \mathcal O(n^{3})。

Accepted Code