题意

我们有一个环形蛋糕，被切成 $N$ 块，每块大小 $A_i$ 互不相同。两个玩家轮流取蛋糕，规则如下：

1. JOI 君先选任意一块
2. IOI 酱开始，两人交替选择
3. 可选条件：只有某块蛋糕的相邻蛋糕中至少有一块已被取走，该块才能被选
4. 选择策略：
   • IOI 酱：总是选当前可选中最大的
   • JOI 君：可以自由选择（要最大化自己的总收益）

目标：求 JOI 君能获得的最大总价值。

关键观察

1. 游戏过程分析

• 初始时所有蛋糕相邻，没有蛋糕可选（除了 JOI 君第一次的任意选择）
• JOI 君第一次选择后，该蛋糕的两侧蛋糕变为可选
• 之后每次选择都会"释放"新的可选蛋糕（如果相邻的蛋糕还没被选）

2. 环形转线性

JOI 君的第一次选择将环形蛋糕断开，转化为线性序列：

• 假设 JOI 君选择了第 $i$ 块蛋糕
• 那么剩下的蛋糕形成一个线性序列：$A_{i+1}, A_{i+2}, \ldots, A_N, A_1, \ldots, A_{i-1}$

3. 可选蛋糕的性质

在游戏过程中，可选的蛋糕始终是当前序列的两端：

• 初始时只有两端的蛋糕可选（因为中间的蛋糕两边都还有蛋糕）
• 每次选择一端后，相邻的蛋糕变为可选

算法思路：区间动态规划

状态设计

设 $dp[l][r]$ 表示在当前线性区间 $[l, r]$ 上进行游戏时，当前玩家能获得的最大价值。

由于两个玩家的策略不同，我们需要知道当前是哪个玩家在操作。

更精确的状态设计

设 $f(l, r, turn)$ 表示在区间 $[l, r]$ 上，如果当前是玩家 $turn$（0=IOI酱，1=JOI君）操作，该玩家能获得的最大价值。

状态转移

基本情况：当 $l > r$ 时，区间为空，返回 0。

当前玩家是 IOI 酱（策略固定）：

• 比较 $A_l$ 和 $A_r$，选择较大的那个
• 如果 $A_l > A_r$：选择左端，获得 $A_l$，然后 JOI 君在 $[l+1, r]$ 上操作
• 否则：选择右端，获得 $A_r$，然后 JOI 君在 $[l, r-1]$ 上操作

当前玩家是 JOI 君（自由选择）：

• 选择左端：获得 $A_l$ + IOI酱在 $[l+1, r]$ 上操作时 JOI 君的收益
• 选择右端：获得 $A_r$ + IOI酱在 $[l, r-1]$ 上操作时 JOI 君的收益
• 取两者最大值

算法步骤

1. 枚举 JOI 君的第一次选择 $i$（$1 \leq i \leq N$）
2. 构造线性序列：将环形蛋糕断开，形成长度为 $N-1$ 的线性序列
3. 计算 DP：在构造的线性序列上计算 JOI 君能获得的最大价值
4. 累加第一次选择的价值：$A_i$ + 线性序列上的收益
5. 取所有情况的最大值

复杂度分析

• 状态数：$O(N^2)$（区间 DP）
• 单次 DP：$O(N^2)$
• 总复杂度：$O(N^3)$（需要枚举第一次选择）

优化：实际上可以只做一次环形 DP，复杂度 $O(N^2)$。

计算过程： 枚举JOI君的第一次选择：

• 选择A[1]=8：获得8 + 在[2,3,4,5]上IOI先手的收益
• 选择A[4]=10：获得10 + 在[5,1,2,3]上IOI先手的收益
• 选择A[0]=2：获得2 + 在[1,3,4,5]上IOI先手的收益
• 等等...

最终找到最优解：选择8，然后按8→2→9→10→1的顺序，总价值18

总结

这道题的关键在于：

1. 识别环形结构，通过破环成链处理
2. 设计博弈DP状态，考虑两个玩家的不同策略
3. 理解游戏过程，可选蛋糕始终是当前区间的两端

算法时间复杂度 $O(N^2)$，空间复杂度 $O(N^2)$，能够处理 $N \leq 2000$ 的数据规模。