Typical DP Contest B: ゲーム (動的計画法)

問題

B: ゲーム - Typical DP Contest | AtCoder

解法

お互いに最善を尽くす時、dp[i][j]の前の手はdp[i-1][j]またはdp[i][j-1]になっているはずなので、それで計算する。

コード

import java.io.IOException;

public class Main {

	public static void main(String[] args) {
		int A = nextInt();
		int B = nextInt();

		int[] a = new int[A];
		int[] b = new int[B];
		for (int i = 0; i < A; i++) {
			a[i] = nextInt();
		}
		for (int i = 0; i < B; i++) {
			b[i] = nextInt();
		}

		int[][] dp = new int[A + 1][B + 1];// dp[i][j]aをi枚、bをj枚ひいた状態で最大の点数
		int[][] sum = new int[A + 1][B + 1];// dp[i][j]aをi枚、bをj枚ひいた状態での点数の和
		for (int i = 0; i < dp.length; i++) {
			if (i > 0) {
				sum[i][0] = sum[i - 1][0] + a[A - i];
			}
			for (int j = 0; j < dp[i].length; j++) {
				if (j > 0) {
					sum[i][j] = sum[i][j - 1] + b[B - j];
				}
				if (i > 0) {
					dp[i][j] = sum[i][j] - dp[i - 1][j];
				}
				if (j > 0) {
					dp[i][j] = Math.max(dp[i][j], sum[i][j] - dp[i][j - 1]);
				}
			}

		}

		System.out.println(dp[A][B]);
	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}

}