POJ 2068 Nim 题解《挑战程序设计竞赛》

POJ 2068 Nim 

团体尼姆赛：传统的尼姆游戏由两名玩家进行，在一堆石头中，双方轮流取走任意合法数量块石头，取走最后一块石头的玩家落败。多人尼姆游戏将参赛人数拓展至两个队伍，每支队伍有n名队员交错入座，单次分别能最多取走M_i块石头，取走S块石头中的最后一块的队伍失败，求第一支队伍是否有必胜策略？

4.2找出游戏的必胜策略 

推理与动态规划算法 

动态规划地搜索整个状态树，定义

win[k][j][i]:=第k支队伍在轮到第j名队员且剩余i块石头的状态

如果i等于0，那么这就是必胜态。以此为初始状态往i=S的方向递推，递推规则为：如果当前状态的后续状态中有一个为必败态，则当前状态为必胜态。理解起来很简单，后续状态指的是对方的状态，只要对方有一个必败态，我方就可以转移到此后续状态，让对方落败，我方取胜。

#include <iostream>
using namespace std;

const int MAX_N = 10;
const int MAX_S = 1 << 13;

int n, S;
int M[2][MAX_N];
bool win[2][MAX_N][MAX_S];             // win[k][j][i]:=第k支队伍在轮到第j名队员且剩余i块石头的状态

bool input()
{
    scanf("%d%d", &n, &S);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d%d", M[0] + i, M[1] + i);
    }

    return n > 0;
}

bool solve()
{
    for (int i = 0; i <= S; ++i)         // 石头数量
    {
        for (int k = 0; k < 2; ++k)          // 队伍编号
        {
            for (int j = 0; j < n; ++j)       // 队员编号
            {
                if (i == 0)
                {
                    win[k][j][i] = true;   // 没有石头，必胜态
                    continue;
                }
                win[k][j][i] = false;
                const int nxt_k = k ^ 1;                     // 下一支队伍的编号
                const int nxt_j = (k == 1 ? (j + 1) % n : j);     // 下一个队员的编号
                for (int t = 1; t <= M[k][j] && i - t >= 0; ++t)   // 尝试拿走1到M[k][j]个石头
                {
                    win[k][j][i] |= !win[nxt_k][nxt_j][i - t];    // 只要后续状态有一个必败态，则当前为必胜态
                }
            }
        }
    }

    return win[0][0][S];
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    while (input())
        puts(solve() ? "1" : "0");
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2068 Nim 题解《挑战程序设计竞赛》