C++

C++ – 博弈 状压 DP

_Redstone_c_

题目传送门

大体题意

Alice 和 Bob 在玩一个游戏，Alice是先手，Bob是后手
给出一个数字序列，Alice和Bob每回合可以从中取出一个数
当序列变为不下降序列时，上一回合的玩家获胜

输入

第一行为 T[1<=T<=100] ，组数。
每组第一行为 N[2<=N<=15] ，序列长度。
后面是一个长度为 N 的序列 A ，其中 [1<=Ai<=N]。

样例
2
3
1 3 2
5
5 3 2 1 4

输出

对应每组的答案，获胜玩家。

样例
Alice
Bob

思路

博弈部分

暴力 DFS ，判断每种状态。[因为有记忆化，所以是DP] 博弈中我们已经证明这题可以用一个图表示，且一个节点的子节点中如果有一个是先手败，则这个节点为先手胜。首先我们要知道如何判断当前是哪一种状态，从叶子节点开始，先会判断序列是否为不下降序列[用到了状压，详细看下面]。

判断函数

arr 为序列，len 为序列长度，k 为当前状态，返回值为序列是否不下降。

bool istrue(int* arr, int len, int k) {
    int temp = -1;
    for(int i = 0; i < len; i++) {
        if(!getbit(k, i)) continue;
        if(temp >= arr[i]) return false;
        else temp = arr[i];
    }
    return true;
}

DFS函数

sg 为答案存储[就是DP数组]，arr 为序列，k 为当前状态，len 为序列长度。

int dfs(int* sg, int* arr, int k, int len) {
    if(sg[k] != -1) return sg[k];
    if(istrue(arr, len, k)) return sg[k] = 0;
    sg[k] = 0;
    for(int i = 0; i < len; i++) {
        if(!getbit(k, i)) continue;
        if(!dfs(sg, arr, setbit(k, i), len))
            sg[k] = 1;
    }
    return sg[k];
}

状态压缩部分

为了方便记录每种状态，我们用一个整形变量的二进制[倒数第i位为1，则对应序列中的第i位存在的，反之，则是已经被删除的]表示目前的状态，就是状压。

获取整形第i位

x 为整形变量，i 为倒数第几位，返回值为其值。

bool getbit(int x, int i) {
    return x >> i & 1;
}
对整形第i位取反

x 为整形变量，i 为倒数第几位，返回值为修改后的整形变量。

int setbit(int x, int i) {
    return x ^ (1 << i);
}

完整代码

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 16;
const int MAXK = (int)pow(2.0, MAXN);
bool getbit(int x, int i) {
    return x >> i & 1;
}
int setbit(int x, int i) {
    return x ^ (1 << i);
}
bool istrue(int* arr, int len, int k) {
    int temp = -1;
    for(int i = 0; i < len; i++) {
        if(!getbit(k, i)) continue;
        if(temp >= arr[i]) return false;
        else temp = arr[i];
    }
    return true;
}
int dfs(int* sg, int* arr, int k, int len) {
    if(sg[k] != -1) return sg[k];
    if(istrue(arr, len, k)) return sg[k] = 0;
    sg[k] = 0;
    for(int i = 0; i < len; i++) {
        if(!getbit(k, i)) continue;
        if(!dfs(sg, arr, setbit(k, i), len))
            sg[k] = 1;
    }
    return sg[k];
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int len;
        scanf("%d", &len);
        int arr[MAXN];
        for(int i = 0; i < len; i++)
            scanf("%d", &arr[i]);
        int sg[MAXK];
        memset(sg, -1, sizeof sg);
        dfs(sg, arr, (int)pow(2.0, len) - 1, len);
        printf("%s\n", sg[(int)pow(2.0, len) - 1] ? "Alice" : "Bob");
    }
    return 0;
}

发表回复