题目描述

在主城站街很久之后，小萌决定不能就这样的浪费时间虚度青春，他打算去打副本。
这次的副本只有一个BOSS，而且BOSS是不需要击杀的，只需要和它比智力…….
BOSS会列出一正整数的序列，由小萌先开始，然后两个人轮流从序列的任意一端取数，取得的数累加到积分里，当所有数都取完，游戏结束。
假设小萌和BOSS都很聪明，两个人取数的方法都是最优策略，问最后两人得分各是多少。

输入

第一行：一个正整数N（2 ≤ N ≤ 100），表示序列中正整数的个数。
第二行至末尾：用空格隔开的N个正整数（1 ≤ a[i] ≤ 200）

输出

只有一行，用空格隔开的两个数，小萌的得分和BOSS的得分。

样例输入

6
4 7 2 9 5 2

样例输出

18 11

参考

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define rep(i, l, r) for(int i = l; i <= (int)r; i ++)
#define debug(a) cout << #a << " = " << a << '\n';
#define PII pair<int, int>
const int N = 1e2 + 2;

int a[N], f[N][N];
//f[i][j] : [i, j] 状态下玩家螚得到的最大分数(这个状态玩家是否先手已经是确定的, 由递归过程决定)

int dfs(int left, int right, bool isTurn) {
    if(f[left][right])
        return f[left][right];
    if(left == right) {
        if(isTurn)
            return f[left][right] = a[left];
        else
            return f[left][right] = 0;
    }
    if(isTurn)//玩家先手, 取最优的
        return f[left][right] = max(dfs(left + 1, right, !isTurn) + a[left], dfs(left, right - 1, !isTurn) + a[right]);
    else      //因为对方足够聪明, 取较小的
        return f[left][right] = min(dfs(left + 1, right, !isTurn),           dfs(left, right - 1, !isTurn)); 
}
main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int tot = 0;
    rep(i, 1, n) {
        cin >> a[i];
        tot += a[i];
    }
    int player = dfs(1, n, true);
    cout << player << " " << tot - player << '\n';
    return 0;
}