2016年蓝桥杯java B组第9题取球博弈

import java.util.Scanner;

class Problem {
	private int N;
	private char[][][] dp;
	private int[] n = new int[3];
	private int min = Integer.MAX_VALUE;

	Problem(int N, int[] n) {
		this.N = N;
		this.n = n;
		init();
	}

	private void init() {
		dp = new char[2][N + 1][N + 1];
		for (int i = 0; i < 3; i++) {
			min = Math.min(min, n[i]);
		}
	}

	// p是player的意思
	// dp[p][A][B]表示先手方取了A个球，后手方取了B个球
	// 现在轮到玩家p，最后先手方的输赢情况
	char dfs(int p, int A, int B) {
		if (dp[p][A][B] != '\u0000')
			return dp[p][A][B];

		// 没有球可取了，判输赢
		if (N - A - B < min) {
			if ((A & 1) == 1 && (B & 1) == 0) // A奇B偶，A胜
				dp[p][A][B] = '+';
			else if ((A & 1) == 0 && (B & 1) == 1) // B奇A偶，B胜
				dp[p][A][B] = '-';
			else
				dp[p][A][B] = '0'; // A没胜B也没胜，说明平

			return dp[p][A][B];
		}

		if (p == 0) { // 0号玩家，即先手一方
			boolean flag = false;
			for (int i = 0; i < 3; i++) {
				if (A + n[i] + B <= N) {
					// 1号玩家说他输，即0号玩家赢
					if (dfs(1, A + n[i], B) == '+')
						return dp[0][A][B] = '+';
					// 1号玩家说平，但0号玩家可能还有能赢的选择
					else if (dfs(1, A + n[i], B) == '0')
						flag = true;
				}
				if (flag)
					dp[0][A][B] = '0'; // 平
				else
					dp[0][A][B] = '-'; // 0号玩家输
			}
		} else if (p == 1) { // 1号玩家，即后手一方
			boolean flag = false;
			for (int i = 0; i < 3; i++) {
				if (A + n[i] + B <= N) {
					// 0号玩家说他输
					if (dfs(0, A, B + n[i]) == '-')
						return dp[1][A][B] = '-';
					// 0号玩家说平，但1号玩家可能还有能赢的选择
					else if (dfs(0, A, B + n[i]) == '0')
						flag = true;
				}
			}
			if (flag)
				dp[1][A][B] = '0'; // 平
			else
				dp[1][A][B] = '+'; // 1号玩家赢
		}
		return dp[p][A][B];
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] n = new int[3];
		for (int i = 0; i < 3; i++) {
			n[i] = sc.nextInt();
		}
		boolean flag = true;
		for (int x = 0; x < 5; x++) {
			int N = sc.nextInt();
			Problem pb = new Problem(N, n);
			if (flag) {
				System.out.print(pb.dfs(0, 0, 0));
				flag = false;
			} else {
				System.out.print(" " + pb.dfs(0, 0, 0));
			}
		}
		sc.close();
	}
}