首页 > 代码库 > POJ 2068 Nim
POJ 2068 Nim
链接：
http://poj.org/problem?id=2068
题意：
传统的Nim游戏由两名玩家进行，在一堆石头中，双方轮流取走任意合法数量块石头，取走最后一块石头的玩家落败。
多人Nim游戏将参赛人数拓展至两个队伍，每支队伍有n名队员交错入座，单次分别能最多取走Mi块石头，取走S块石头中的最后一块的队伍失败，
求第一支队伍是否有必胜策略？
题解：
dp[i][j]表示第i个人取，还有j块石头 。
当j为0的时候，没有石头，这时候是胜，为1。
后继中有必败态的为必胜态。
代码：
31 int dp[30][10010];32 int n, s, a[30];33 34 int solve(int idx, int remain) {35 if (dp[idx][remain] != -1) return dp[idx][remain];36 if (remain == 0) return dp[idx][remain] = 1;37 dp[idx][remain] = 0;38 rep(i, 1, min(a[idx], remain) + 1) 39 if (!solve((idx + 1) % (2 * n), remain - i)) 40 dp[idx][remain] = 1;41 return dp[idx][remain];42 }43 44 int main() {45 while (cin >> n, n) {46 cin >> s;47 rep(i, 0, 2 * n) cin >> a[i];48 memset(dp, -1, sizeof(dp));49 cout << solve(0, s) << endl;50 }51 return 0;52 }
POJ 2068 Nim
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。