二十二 1388. 游戏 (区间DP|博弈论)

388. 游戏 (区间DP|博弈论)

思路：在最坏情况下考虑问题，每个人都选择对自己有利的情况，dp[i][j]指的是对方获得的分差，分值总和固定为sum，因此我方方差越大，对方的分值就越小。最后A+B=sum，A-B=diff。

import java.util.*;


public class Main {
    private static int N, sum, diff;
    private static int[] g;
    private static int[][] dp;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        sum = 0;
        g = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            g[i] = sc.nextInt();
            sum += g[i];
        }
        dp = new int[N + 2][N + 2];
        for (int len = 1; len <= N; len++) {
            for (int i = 1; i + len - 1 <= N; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(g[i] - dp[i + 1][j], g[j] - dp[i][j - 1]);
            }
        }
        diff = dp[1][N];
        System.out.println((sum + diff) / 2 + " " + (sum - diff) / 2);
    }
}