Alice和Bob在玩这样一个游戏。给定k个数字a[1],a[2],…,a[k]。一开始，有x枚硬币，Alice和Bob轮流取硬币。每次所取硬币的枚数一定要在a[1],a[2],…,a[k]当中。Alice先取，取走最后一枚硬币的一方获胜。当双方都采取最优策略时，谁会获胜？题目假定a[1],a[2],…,a[k]中一定有1。
限制条件：
1<=x<=10000
1<=k<=100
1<=a[i]<=x
输入：
x=9
k=2
a={1,4}
输出：
Alice
思路：
按照我们常人的想法，当前状态有三种状态 必胜，必败，或者不确定；当对了两个聪明的人来说就只有两种情况：必胜，必败；下面请看必胜态，必败态的解释；
必败态：有x枚硬币，有a[0]~a[k-1]中取法，当前不管你按那种取法取，都在人家的掌控之中，都得按照人家的节奏来，因为人家和你都是一样聪明；也就是说x-a[i] (0<=i<k)为必胜态（从x-a[i]取的人掌控着战局），x就是必败态；
必胜态：当前取的人，按照自己聪明的想法取，他取过之后能使得对方不管按那种方法取，都赢不了，也就是说对方不管按那种方法取，剩下的硬币数，还是必胜态，也就是说只要自己一直按照聪明的想法取，不管对方多么聪明都无计可施；
当前为x枚硬币
当x==0时，为必败态；
当x>0时
若对于某个i （0<=i<k且x-a[i]>=0）x-a[i] 为必败态，那么x是必胜态；
若对于任意的i（0<=i<k且x-a[i]>=0）x-a[i]为必胜态，那么x就是必败态；
写程序，算是用了动态规划的思想，从小到大推出是必胜态，还是必败态；
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define Max 10010
bool win[Max];
int main()
{
int i,j,x,k;
int a[110];
while(~scanf("%d%d",&x,&k))
{
for(i=0;i<k;i++)
scanf("%d",&a[i]);
win[0] = false;
for(j=1;j<=x;j++)
{
win[j] = false;
for(i=0;i<k;i++)
{
if(j>=a[i])
win[j] |= !win[j-a[i]]; //表述法一：当j>=a[i]时，只要有一个a[i],使得j-a[i]为必败态，那么j就为必胜态；
//if(j>=a[i]&&!win[j-a[i]]) // 表述法二：和上面一样；
// win[j] = true;
/*if(j>=a[i]) //表述法三：
{
if(win[j-a[i]])
continue;
else break;
}*/
}
/*if(i>=k) win[j] = false; // 取任意一种情况，剩下的都为必胜态，此时就为必败态；
else win[j] = true; // 只要有一种情况取后，剩下的为必败态，那么此时就是必胜态（一直按照自己聪明的想法取）
*/
}
if(win[x]) printf("Alice\n");
else printf("Bob\n");
}
return 0;
}