http://poj.org/problem?id=1143
Description
Input
Output
Sample Input
2 2 5 2 2 3 5 2 3 4 5 6 0
Sample Output
Test Case #1 The winning moves are: 2 Test Case #2 There‘s no winning move. Test Case #3 The winning moves are: 4 5 6
/**
poj 1143 状态压缩dp
题目大意：给定一组数据a[],2~20之内的数在数组里出现过的是可以选的，一个数一旦被选，那么它的倍数以及与其倍数（整数倍）与所有
已选数的倍数（整数倍）的和相等的数不能再选，两人轮流选择，问是否有一个数据第一个人选了之后无论第二个人怎么选第一
个人都会胜的数。（二者都会采取最优选法）
解题思路：题目只有20个数，因此我们把所有的状态压缩到一个二进制数里，然后枚举选择哪个数，如果选择该数后，另一个人没有可以胜
的选法，那么该数字就是一个可行点。
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
int a[25],ans[25],dp[(1<<20)+3];
int n;
bool vis[(1<<20)+3];
bool judge(int i,int j,int st)
{
return ((1<<(a[j]-a[i]-1))&(~st))&&(a[j]-a[i]!=1)||((a[j]+1)%(a[i]+1)==0);
}
bool solve(int num,int state)///um:还剩多少数字可选，state：当前选择情况，二进制压缩的数
{
if(vis[state])return dp[state];///记忆化，如果已经判断过直接返回
vis[state]=true;
if(state==0)return 0;///没数可选，必输
if(num==1) return dp[state]=1;///只剩一个数，必胜
int key=0;
for(int i=0;i<n;i++)
{
int st=state;
if((1<<a[i])&state)///枚举当前去掉的点
{
for(int j=i+1;j<n;j++)
{
if(((1<<a[j])&st)&&judge(i,j,st))///去除选择i点后i的倍数点和其与已选数倍数和的组成点
{
st^=(1<<a[j]);
}
}
key=solve(num-1,st^(1<<a[i]));
if(!key)return dp[state]=1;///若后者必输，则i点可行
}
}
return dp[state]=0;
}
int main()
{
int tt=0;
while(~scanf("%d",&n))
{
if(n==0)break;
memset(vis,0,sizeof(vis));
memset(a,0,sizeof(a));
int state=0,count=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
a[i]--;
state^=(1<<a[i]);
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
int st=state;
for(int j=i+1;j<n;j++)
{
if(judge(i,j,st)&&(st&(1<<a[j])))
st^=(1<<a[j]);
}
if(solve(n-1,(1<<a[i])^st)==0)
{
ans[count++]=a[i]+1;
}
}
printf("Test Case #%d\n",++tt);
if(!count)
printf("There's no winning move.\n\n");
else
{
printf("The winning moves are:");
for(int i=0;i<count;i++)
{
printf(" %d",ans[i]);
}
printf("\n\n");
}
}
return 0;
}
原文：http://blog.csdn.net/lvshubao1314/article/details/44257119