【博弈论】【蓝桥杯】

取球博弈 蓝桥杯

深搜+记忆化
代码原文章：大佬代码

package 考前训练;

public class _取球博弈 {
	public static int[] a;
	public static int min;
	public static int[][][] cash = new int[1001][2][2];

	public static int f(int rest, int havenum, int othernum) {
		//输赢判断
		if (rest < min) {
			if (havenum % 2 != 0 && othernum % 2 == 0)
				return 2;
			if (havenum % 2 != 0 && othernum % 2 != 0)
				return 1;
			if (havenum % 2 == 0 && othernum % 2 == 0)
				return 1;
			return -1;
		}
		boolean equalflag = false;
		for (int sel : a) {
			if (sel > rest)
				continue;
			int result;
			//记忆化搜索
			if (cash[rest - sel][othernum % 2][(havenum + sel) % 2] != 0)
				result = cash[rest - sel][othernum % 2][(havenum + sel) % 2];
			else {
				result = f(rest - sel, othernum, havenum + sel);
				cash[rest - sel][othernum % 2][(havenum + sel) % 2] = result;
			}
			//对面输了，我赢了
			//赢了一次后面的情况就可以不进行判断了
			if (result == -1)
				return 2;
			//平了
			if (result == 1)
				equalflag = true;
		}
		//能走到这一步说明没赢，判断一下平没评
		if (equalflag)
			return 1;
		else
			return -1;
	}

	public static void main(String[] args) {
		int[] b = { 1, 2, 3, 4, 5, 900 };
		a = new int[] { 1, 2, 3 };
		min = 1;
		for (int total : b) {
			char ch = 0;
			switch (f(total, 0, 0)) {
			case -1:
				ch = '-';
				break;
			case 1:
				ch = '0';
				break;
			case 2:
				ch = '+';
				break;
			}
			System.out.print(ch);
		}
	}
}

最后

以上就是悦耳香菇为你收集整理的【博弈论】【蓝桥杯】的全部内容，希望文章能够帮你解决【博弈论】【蓝桥杯】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。