硬币游戏 1（博弈）

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

思路：下面来考虑当轮到自己时，还有j枚硬币时的胜负情况。

1）题目规定取光所有的硬币就获胜，这等价于轮到自己时如果没有硬币了就失败。因此，j=0时是必败态。

2）如果对于某个i(1<=i<=k)，j-a[i]是必败态的话，j就是必胜态。（如果当前有j枚硬币，只要取走a[i]枚对手就必败->自己必胜）。

3）如果对于任意的i(1<=i<=k)，j-a[i]都是必胜态的话，j就是必败态。（不论怎么取，对手都必胜->自己必败）。

根据这些规则，我们就能利用动态规划算法按照j从小到大的顺序计算必胜态必败态。只要看x是必胜态还是必败态，就能知道谁会获胜了。

像这样，通过考虑各个状态的胜负条件，判断必胜态和必败态，是有胜败的游戏的基础。

代码：

//输入
int x,k,A[max_k];

//动态规划所用的数组
Bool win[max_x+1];

void solve()
{
    //轮到自己时没有硬币了，则失败
    win[0]=false;

    for(int j=1;j<=x;j++)
    {
         //如果可以让对手到达必败态，则必胜
         win[j]=false;
         for(int i=0;i<k;i++)
               win[j]|=A[i]<=j&&!win[j-A[i]];
    }

    if(win[x])   puts(“Alice”);
    else   puts(“Bob”);
}