题意:一开始有s个石子,2n个人轮流取石子,每个人有个最大能取数目,2n个人奇数一队,偶数一队,取到最后一个石子的队输,问谁赢
思路:记忆化搜索,每个人取的时候对应的后继状态如果有一个必败态,则该状态为必胜态,如果都是必胜态,则该状态为必败态
代码:
#include <stdio.h> #include <string.h> 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; }
UVA 1559 - Nim(博弈dp),布布扣,bubuko.com
原文:http://blog.csdn.net/accelerator_/article/details/37886953