题目2267:蓝桥杯2016年第七届真题-取球博弈

#include<iostream>
#include<algorithm>
using namespace std;
int n[5], vis[1000][2][2];

int dfs(int x, int f, int s) {
if(vis[x][f%2][s%2] != 2) {
return vis[x][f%2][s%2];
}

if(x < n[1]) { // 不能取球了
if((f%2 == 1) && (s%2 == 0)) return 1;
else if((f%2 == 0) && (s%2 == 1)) return -1;
else return 0;
}

int res;
bool ping = false; // 记录是否有平局可能

for(int i = 1; i <= 3; i++) {
if(x - n[i] >= 0) {
res = dfs(x - n[i], s, f + n[i]);

if(res == -1) { // 对手输，我赢
vis[x][f%2][s%2] = 1;
return 1;
}
if(res == 0) { // 有平局可能
ping = true;
}
}
}

if(ping) { // 没有必胜，但有平局
vis[x][f%2][s%2] = 0;
return 0;
}

// 所有选择都导致对手赢
vis[x][f%2][s%2] = -1;
return -1;
}

int main() {
cin >> n[1] >> n[2] >> n[3];
sort(n+1, n+4);//排序范围是 n[1]、n[2]、n[3]

for(int i = 1; i <= 5; i++) {
int x;
cin >> x;

// 初始化vis数组
for(int j = 0; j <= x; j++) {
vis[j][0][0] = vis[j][0][1] = vis[j][1][0] = vis[j][1][1] = 2;
}

int ans = dfs(x, 0, 0);

if(ans == 1) cout << "+ ";
else if(ans == 0) cout << "0 ";
else cout << "- ";
}

return 0;
}