1388. 游戏

状态表示：
\(f[i][j]\) 表示在区间 \([i,j]\) 时，先手和后手的最大差值得分。
状态转移：

• 当取 \(w[i]\) 时，\(f[i][j]=w[i]?f[i+1][j]\)。
• 当取 \(w[j]\) 时，\(f[i][j]=w[j]?f[i][j?1]\)。

\(f[i][j]\) 表示在区间为 \([i, j]\) 时 A 与 B 得分差的最大值，则\(f[i + 1][j]\) 表示区间为 \([i + 1, j]\) 时 B 与 A 得分差的最大值，取一下相反数即可得到区间为\([i+1, j]\)时 A 与 B 得分差的最大值。

边界：
\(f[i][i] = w[i]\)

const int N = 110;
int a[N];
int f[N][N];
int n;

int main()
{
    cin >> n;

    int sum = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];

    for(int i = n; i; i--)
        for(int j = 1; j <= n; j++)
            if(i == j) f[i][j] = a[i];
            else f[i][j] = max(a[i] - f[i + 1][j], a[j] - f[i][j - 1]);
            
    cout << (sum + f[1][n]) / 2 << ‘ ‘ << (sum - f[1][n]) / 2 << endl;
    //system("pause");
    return 0;
}

1388. 游戏

原文：https://www.cnblogs.com/fxh0707/p/14933737.html