0%

Leetcode464 简单博弈

Posted on

题面描述 我能赢吗

给定 $1 \leq maxn \leq 20$ 和 $0 \leq x \leq 300$ 进行平等博弈。起初桌子上有 $1$ 到 $maxn$ 金额的硬币，双方轮流取一枚硬币，当取出硬币总和不小于 $x$ 时获胜。问先手是否必胜。
属于基本的博弈问题，开bitset记录当前还能选的硬币，记忆化搜索。

奇怪的是，出题人认为初始 $x=0$ 先手属于必胜态，被我特判掉了。显然出题人对博弈论没有很好的理解。

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
class Solution {
5
protected:
6
    int n;
7
    unordered_map<bitset<21>,bool> vis[310];
8
9
    bool dfs(int sum,bitset<21> cur){
10
        if (sum<=0) return false;
11
        auto p=vis[sum].find(cur);
12
        if (p!=vis[sum].end()) return (*p).second;
13
        bitset<21> nxt;
14
        for (int i=n;i>=1;--i){
15
            if (cur[i]){
16
                nxt=cur;
17
                nxt.reset(i);
18
                if (!dfs(sum-i,nxt)){
19
                    return vis[sum][cur]=true;
20
                }
21
            }
22
        }
23
        return vis[sum][cur]=false;
24
    }
25
26
public:
27
    bool canIWin(int maxn, int sum) {
28
        if (sum==0) return true;
29
        if (sum>(1+maxn)*maxn/2) return false;
30
        n=maxn;
31
        for (int i=0;i<=sum;++i){
32
            vis[i].clear();
33
        }
34
        bitset<21> tmp;
35
        tmp.reset();
36
        for (int i=1;i<=n;++i){
37
            tmp.set(i);
38
        }
39
        return dfs(sum,tmp);
40
    }
41
};