UVA 1559 - Nim

题目链接

题意：一开始有s个石子，2n个人轮流取石子，每个人有个最大能取数目，2n个人奇数一队，偶数一队，取到最后一个石子的队输，问谁赢

思路：记忆化搜索，每个人取的时候对应的后继状态如果有一个必败态，则该状态为必胜态，如果都是必胜态，则该状态为必败态

代码：

#include 
  
   
#include 
   
     int n, s, m[25], dp[25][10005]; int dfs(int now, int state) { if (dp[now][state] != -1) return dp[now][state]; if (state == 0) return dp[now][state] = 1; dp[now][state] = 0; for (int i = 1; i <= m[now]; i++) { if (state < i) break; if (!dfs((now + 1) % (2 * n), state - i)) dp[now][state] = 1; } return dp[now][state]; } int main() { while (~scanf("%d", &n) && n) { memset(dp, -1, sizeof(dp)); scanf("%d", &s); for (int i = 0; i < 2 * n; i++) scanf("%d", &m[i]); printf("%d\n", dfs(0, s) ? 1 : 0); } return 0; }