硬币游戏1——打表&&记忆化搜索

题目

Alice和Bo在玩这样一个游戏，给定 $k$ 个数字 $a_1, a_2,..,a_k$.一开始有 $x$ 枚硬币，Alice和Bob轮流取硬币。每次所取的硬币的枚数一定要在 $k$ 个数当中。Alice先取，取走最后一枚的获胜。当双方都采取最有策略时，谁会获胜？假设 $k$ 个数中一定有1.（$1 \leq x\leq 1000,1\leq k\leq 100$）

分析

至少，可以爆搜。加个记忆化就过了。

• $x=0$ 是必败态
• 如果对于某个 $i$，$x-a_i$ 是必败态，$x$ 就是必胜态
• 如果对于任意的 $i$，$x-a_i$ 都是必胜态，则 $x$ 是必败态

#include<bits/stdc++.h>

using namespace std;

const int maxn =  + ;

const int maxx =  + ;

int x, n, a[maxn];

int res[maxx];

int dfs(int x)

{

    //printf("x:%d\n", x);

    int& ret = res[x];

    if(ret)  return ret;

    if(x == )  return ret=-;

    bool flag = false;

    for(int i = ;i < n;i++)

    {

        if(x >= a[i])

        {

            int tmp = dfs(x-a[i]);

            if(tmp == -)  return ret=;

            if(tmp == )  flag = true;

        }

    }

    return ret = (flag ?  : -);

}

int main()

{

    scanf("%d%d", &x, &n);

    for(int i = ;i < n;i++)  scanf("%d", &a[i]);

    //printf("%d\n", dfs(x));

    int t = dfs(x);

    if(t == )  printf("");

    else  printf("-1\n");

}

其实，上面代码就是DP的记忆化搜索，写成递推的形式：

#include<bits/stdc++.h>

using namespace std;

const int maxn =  + ;

const int maxx =  + ;

int x, n, a[maxn];

int res[maxx];

void solve()

{

    res[] = -;

    for(int i = ;i <= x;i++)

    {

        res[i] = -;    //易知，这个游戏没有平局

        for(int j = ;j < n;j++)  if(i >= a[j])

            if(res[i-a[j]] == -)  res[i] = ;     //如果可以让后手达到必败态，则先手必胜

    }

}

int main()

{

    scanf("%d%d", &x, &n);

    for(int i = ;i < n;i++)  scanf("%d", &a[i]);

    solve();

    printf("%d\n", res[x]);

    return ;

}