題目大意：
兩個人玩游戲。輪流取數(shù)字，范圍在1~20之間。
規(guī)定：
1. 取過的數(shù)字不能再取。
2. 取過的數(shù)字的倍數(shù)不能再取。
3. 任意個(2)的和不能再取。
當(dāng)某個人發(fā)現(xiàn)沒有數(shù)字可取時，他就輸了。
給出一個“殘局”。問，我現(xiàn)在應(yīng)該怎么取，才能保證勝利。
思路：
其實這個也不是很難的博弈問題。只是搜索就可以解決了。要用位來表示當(dāng)前剩余數(shù)字的狀態(tài)，
方便保存動態(tài)規(guī)劃的結(jié)果。
#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;
}