POJ2068 NIM

2015.01.13 14:55 Tue| 0 visits oi_2015| 2015_刷题日常| Text

Problem

有两队人互相交叉着围坐在堆满石子的圆桌上,每一队都有 n 个人。给出石子的数目 s ,按顺序给出这 2n 个人最多能够拿走的石子数目,拿走最后一个石子的队伍获胜。问最终哪一队能够获胜。

Solution

记忆化搜索:

若轮到某人时,没有剩余石子,则他所在的队伍一定获胜。否则枚举当前人拿走的石子数目,若拿走后对方面临必败局势,则当前队伍存在必胜局势。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, s, a[25], f[10000][25];

int dfs(int s, int t)
{
    if (f[s][t] >= 0) return f[s][t];
    if (s == 0) return f[s][t] = 1;
    for (int i = 1; i <= min(a[t], s); ++i)
        if (!dfs(s - i, (t + 1) % (n * 2)))
            return f[s][t] = 1;
    return f[s][t] = 0;
}

int main()
{
    while (cin >> n, n)
    {
        cin >> s;
        for (int i = 0; i < n * 2; ++i)
            cin >> a[i];
        memset(f, -1, sizeof f);
        cout << dfs(s, 0) << endl;
    }
}