Cake Game (USACO Silver 2024 December)

博弈论问题，首先考虑找最优解的策略。

因为蛋糕是偶数个，所以最后一轮必然是B合并两个蛋糕而结束游戏，B得到剩余的所有蛋糕的分数。一共轮数是 $N/2$ 轮，E得到 $N/2-1$ 块蛋糕。

这时我们考虑E的策略，因为E每次从左边或者右边取蛋糕，有没有比每次取更大那块更好的策略？比较容易想到，因为E取的蛋糕总数固定是 $N/2-1$ ，所以E有一个基本的策略，就是取左侧加右侧一共 $N/2-1$ 块加起来最大的组合。

然后我们观察到，B不管做什么，都不可能使得E取得的分数小于上面的策略的结果，如果B试图合并在以上策略中E会取走的蛋糕，结果是会让E的总分更高（因为E会取得更多蛋糕的分值），所以我们得到结论：B没有必要合并本来属于E的蛋糕，因为如果B这样做，就是帮助E提高分数，而降低了自己的分数。

因此，在双方都采取最优策略的情况下，E的分数就是总长为 $N/2-1$ 的前缀和后缀的最大和，B得到中间的所有蛋糕的分数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t,n;
ll psum[500005];
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int a;
            scanf("%d", &a);
            psum[i] = psum[i-1] + a;
        }
        ll ans = 0;
        for (int i = 0; i <= n/2-1; i++) {
            ans = max(ans, psum[i] + psum[n] - psum[n-(n/2-1-i)]);
        }
        printf("%lld %lld\n", psum[n] - ans, ans);
    }
 
    return 0;
}