AcWing 3157. 取球博弈 保存奇偶性
原题链接
简单
作者:
季之秋
,
2021-04-02 15:57:47
,
所有人可见
,
阅读 561
import java.util.*;
public class Main{
private static int[] n = new int[3];
private static int N;
private static char[][][] cache = new char[1000][3][3];
public static char f(int N,int me,int you){
if(cache[N][me][you]!='\0')
return cache[N][me][you]; // 记忆化搜搜
if(N<n[0]){ // 只要一次就选完了,判断奇偶即可
if((me&1)==1&&(you&1)==0){
return cache[N][me][you]='+';
}else if((me&1)==0&&(you&1)==1){
return cache[N][me][you]='-';
}else {
return cache[N][me][you]='0';
}
}
boolean flag = false;
for(int i=0;i<3;i++){
if(N>=n[i]){
char cc = f(N-n[i],you,(n[i]&1)==1?(1-me):me); // 我选n[i]之后总数N-n[i],
// 递归到下一层让别人选,如果n[i]是奇数,加上后使我 (偶 - >奇) || (奇- > 偶),加上偶数我的奇偶性不变
if(cc=='-')
return cache[N][me][you]='+'; // 对方选了之后输了就是我赢了
else if(cc=='0'){
flag = true;
}
}
}
if(flag==true){
return cache[N][me][you]='0'; // 没有赢的局面的话 最好情况就是 互相平局
}else{
return cache[N][me][you]='-'; // 按题意 :如有办法逼平对手就不算输,
// 如有办法赢就必赢, 如果怎么选都是输才算必输(没有平局和赢的情况下才算必输)
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
for(int i=0;i<3;i++){
n[i]=scanner.nextInt();
}
Arrays.sort(n);
for(int i=0;i<5;i++){
N=scanner.nextInt();
char c=f(N,0,0);
System.out.printf("%c ",c);
}
System.out.printf("\n");
}
}