糯米

題目大意：
兩個人玩游戲。輪流取數字，范圍在1~20之間。
規定：
1. 取過的數字不能再取。
2. 取過的數字的倍數不能再取。
3. 任意個(2)的和不能再取。

當某個人發現沒有數字可取時，他就輸了。
給出一個“殘局”。問，我現在應該怎么取，才能保證勝利。

思路：
其實這個也不是很難的博弈問題。只是搜索就可以解決了。要用位來表示當前剩余數字的狀態，
方便保存動態規劃的結果。

#include <stdio.h>

#define N 20

char dp[2][1 << (N + 1)];

__inline int use(int visited, int idx)
{
    int i;

    for (i = 0; i + idx <= N; i++) {
        if (visited & (1 << i))
            visited |= 1 << (i + idx);
    }
    return visited;
}

int dfs(int my_step, int visited)
{
    int i, r;

    if (visited == (1 << (N + 1)) - 1) 
        return !my_step;
    
    r = dp[my_step][visited];
    if (r)
        return r - 1;

    for (i = 2; i <= N; i++) {
        if (visited & (1 << i))
            continue;
        r = dfs(!my_step, use(visited, i));
        if (my_step && r)
            return 1;
        if (!my_step && !r)
            return 0;
    }

    dp[my_step][visited] = !my_step + 1;
    return !my_step;
}

int main()
{
    int n, v, i, arr[24], cnt, t;

    freopen("e:\\test\\in.txt", "r", stdin);

    for (t = 1; scanf("%d", &n), n; t++) {
        v = ((1 << (N + 1)) - 1) & ~2;
        while (n--) {
            scanf("%d", &i);
            v &= ~(1 << i);
        }
        cnt = 0;
        for (i = 2; i <= N; i++) {
            if (v & (1 << i))
                continue;
            if (dfs(0, use(v, i)))
                arr[cnt++] = i;
        }
        printf("Test Case #%d\n", t);
        if (cnt) {
            printf("The winning moves are:");
            for (i = 0; i < cnt; i++) 
                printf(" %d", arr[i]);
            printf("\n");
        } else 
            printf("There's no winning move.\n");
        printf("\n");
    }

    return 0;
}