马贼和金矿

题目

A、B两伙马贼意外地在一片沙漠中发现了一处金矿，双方都想独占金矿，但各自的实力都不足以吞下对方，经过谈判后，双方同意用一个公平的方式来处理这片金矿。处理的规则如下：他们把整个金矿分成n段，由A、B开始轮流从最左端或最右端占据一段，直到分完为止。

马贼A想提前知道他们能分到多少金子，因此请你帮忙计算他们最后各自拥有多少金子?（两伙马贼均会采取对己方有利的策略）

思路

• 二维数组 dp[i][j] 表示 A 在 i 和 j 段内所能获得的最大值
• 一维数组 sum[i] 表示 1~i 金矿质量和

动态规划方程为：

    dp[i][j] = sum[j] - sum[i-1] + Math.min(dp[i+1][j], dp[i][j-1]);

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {

    static StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        int T = nextInt();
        for (int j = 1; j <= T; j++) {
            int n = nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            int[] res = solve(a);
            System.out.printf("Case #%d: %d %d", j, res[0], res[1]);
        }
    }

    static int[] solve(int[] nums) {
        int len = nums.length;
        int[] sum = new int[len + 1];
        int[][] dp = new int[len + 1][len + 1];
        sum[0] = 0;
        for (int i = 1; i <= len; i++) {
            dp[i][i] = nums[i - 1];
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        for (int i = len - 1; i > 0; i--) { // 从右端开始计算
            for (int j = i; j <= len; j++) {
                dp[i][j] = sum[j] - sum[i - 1] - Math.min(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return new int[]{dp[1][len], sum[len] - dp[1][len]};
    }

    static int nextInt() throws IOException {
        streamTokenizer.nextToken();
        return (int) streamTokenizer.nval;
    }

    static long nextLong() throws IOException {
        streamTokenizer.nextToken();
        return (long) streamTokenizer.nval;
    }
}