第7回ブルーブリッジカップボールゲームの詳細

ボールゲーム
二人でボールを取るゲームをします.
全部でN個のボールがあり、一人一人が交代でボールを取り、毎回集合{n 1,n 2,n 3}のいずれかの数を取ることができる.
ボールを取り続けることができなければ、ゲームは終了します.
この時、奇数球を持った方が勝つ.
2人とも奇数なら引き分けだ.
双方が最も賢い方法を採用していると仮定します.
最初にボールを取った人は必ず勝つことができますか?
この問題をプログラミングして解決する.
入力形式:
1行目の3つの正の整数n 1 n 2 n 3は、1回の取り得る数(0行目の5つの正の整数x 1 x 2...x 5は、5セットの初期球数(0
出力フォーマット:
1行5文字、スペースが分かれています.各セットで先にボールを取った人が勝つかどうかをそれぞれ表しています.
勝てば出力+,
次に、相手を追いつめる方法があれば、0を出力します.
どうしても負けたら出力-
たとえば、次のように入力します.
1 2 3
1 2 3 4 5
プログラムは出力するべきです:
+ 0 + 0 -
たとえば、次のように入力します.
1 4 5
10 11 12 13 15
プログラムは出力するべきです:
0 - 0++
たとえば、次のように入力します.
2 3 5
7 8 9 10 11
プログラムは出力するべきです:
+ 0 0 0 0
考え方:データ量を見て、動的な計画を行う必要があります.そうしないと、小さなデータしかできません.基本的な考え方は以下の通りです.
dp配列を定義し、現在順番になっているプレイヤー、Aプレイヤーの手球数、Bプレイヤーの手球数を格納する保存配列
Aは0、Bは1
現在触っている数が1,2,3ならボール総数は5
先手Aがボールを触る番になったら、今の状況は(0,0,0,5)、2番目と3番目のパラメータは今のAとBの手のボール数です.
Aは1、2、3を探して、触った後の局面を見て、例えば1つのボールを探して、それではこの局面(1、1、0、5)にジャンプするべきで、1はBプレイヤーの番で、Aはすでに触ったことがあって、Aは1つのボールを触ったので、2番目のパラメータは1です
最後に触ることができなければ,現在の局面を判断し,A%2,B%2はそれぞれAとBの手のボールのパリティを判断する.
コード:

import java.util.Scanner;

public class      {
	static int ns[] = new int[3];//    
	static int xs[] = new int[5];//     
	static char dp[][][] = new char[2][1000][1000];//        ，       ，A      ，B             
	
	//       
	public static int min(int a[]) {
		int min=9999;
		for (int i : a) {
			if (min>i) {
				min=i;
			}
		}
		return min;
	}
	 //   ，A      ，B      ,    
	static char dfs(int p,int Aown,int Bown,int totoalNum){
		int min = min(ns);//        
		int rest = totoalNum - Aown - Bown;//          ，   -A    -B     
		if (dp[p][Aown][Bown] != '\u0000') {//java char           \u0000      
			return dp[p][Aown][Bown];//    ，       （    ），      
		}
		if (rest < min) {//      2 ，     1 ，        ，     
			if (Aown % 2 == 1 && Bown % 2 == 0) {//  A B ，  ，  +    A     
				dp[p][Aown][Bown] = '+';  
			}
			else if (Aown % 2 == 0 && Bown % 2 == 1) {//A   
				dp[p][Aown][Bown] = '-';
			}else {
				dp[p][Aown][Bown] = '0';
			}
			return dp[p][Aown][Bown];
		}
		
		if (p==0) {//        A  
			boolean iseq = false;//         
			for (int i = 0; i < ns.length; i++) {//       
				if (rest >= ns[i]) { //     ，      2 ，     1 ，    ，ns[i]           
					if (dfs(1, Aown + ns[i], Bown,totoalNum)=='+') {//           ，            A ，  A   
						return dp[0][Aown][Bown] = '+';
					}else if (dfs(1, Aown + ns[i], Bown,totoalNum) == '0') {//         ，     
						iseq = true;
					}
				}
			}
			//for      ，           
			if (iseq) //    ，       
				dp[0][Aown][Bown] = '0';
			else 
				dp[0][Aown][Bown] = '-';
			
		}
		if (p==1) {//      B  
			boolean iseq = false;
			for (int i = 0; i < ns.length; i++) {
				if (rest >= ns[i]) { //     ，      2 ，     1 ，    ，ns[i]           
					if (dfs(0, Aown , Bown+ ns[i],totoalNum)=='-') {//   A               ， A   ，         
						return dp[1][Aown][Bown] = '-';
					}else if (dfs(0, Aown , Bown+ ns[i],totoalNum) == '0') {//     
						iseq = true;
					}
				}
			}
			//         ，     
			if (iseq) 
				dp[1][Aown][Bown] = '0';
			else 
				dp[1][Aown][Bown] = '+';
			
		}
		return dp[p][Aown][Bown];
		
	}
	
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		for (int i = 0; i < ns.length; i++) {
			ns[i] = scanner.nextInt();
		}
		for (int i = 0; i < xs.length; i++) {
			xs[i] = scanner.nextInt();
		}
		int k;
		for (int i = 0; i < xs.length; i++) {
			dp = new char[2][1000][1000];//            dp  
			k = dfs(0, 0, 0,xs[i]);
			System.out.print((char)k + " ");
		}
	}
}

まとめ:+、-は絶対性を持っていて、+はAが勝つことを代表して、-はAが負けることを代表します.
if (dfs(1, Aown + ns[i], Bown,totoalNum)=='+') {
        return dp[0][Aown][Bown] = '+';
上のAはA(自分)が勝つ局面があるかどうかを探しています.
if (dfs(0, Aown , Bown+ ns[i],totoalNum)=='-') {
return dp[1][Aown][Bown] = '-';
このBは次のジャンプ局面でAを負ける局面、すなわちB(自分)が勝つ局面を探している.
A,Bは両方とも相手に負けたり、自分で勝つことができる局を探して、一つ見つけたらこのような取り方を採用して、見つからないなら和の局面があるかどうかを見て、二度と見つからないのは負けです
なぜ開局ごとにdp配列を再初期化しなければならないのか、前のデータは繰り返し使えないのか.
だめです.同じdp[0][1][0]でも始球数が違う場合は意味が違いますから.
クリアしなければ、現在の始局球数が5、Aが1つタッチした場合、直前に保持していた始局球数が1、Aが1つタッチした場合を呼び出す
後者は明らかに必勝局で,前者とは結末が違う.