HDU4155 博弈dp

Posted on | In , ,

给六种牌1~6，每种四张，A和B轮流任意选一张牌，谁先让选出的牌和$sum\geq 31$就输，现给出部分已经选的序列，问最优情况下谁赢。

题目链接

题解

  • 选牌的顺序会影响答案，总共状态数为不是很多，考虑爆搜
  • 预处理出所有不合法状态
  • 然后暴力找出所有状态，因为和不会超过31所以总共的状态不会很多
  • 一个状态可以转移到很多状态
  • 考虑先手拿牌则是有胜的状态就转移到胜的状态
  • 考虑后手拿牌肯定不能转移到先手赢的状态

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn = 1e4+7;

char s[maxn];
int dp[5][5][5][5][5][5];

int dfs(int x, int y, int z,int a, int b,int c)
{
    int num=a+b+c+x+y+z;
    int tot=0, cnt=0;
    if(x<4)
    {
        if(dp[x+1][y][z][a][b][c]==-1) dfs(x+1,y,z,a,b,c);
        cnt+=dp[x+1][y][z][a][b][c];
        tot++;
    }
    if(y<4)
    {
        if(dp[x][y+1][z][a][b][c]==-1) dfs(x,y+1,z,a,b,c);
        cnt+=dp[x][y+1][z][a][b][c];
        tot++;
    }
    if(z<4)
    {
        if(dp[x][y][z+1][a][b][c]==-1) dfs(x,y,z+1,a,b,c);
        cnt+=dp[x][y][z+1][a][b][c];
        tot++;
    }
    if(a<4)
    {
        if(dp[x][y][z][a+1][b][c]==-1) dfs(x,y,z,a+1,b,c);
        cnt+=dp[x][y][z][a+1][b][c];
        tot++;
    }
    if(b<4)
    {
        if(dp[x][y][z][a][b+1][c]==-1) dfs(x,y,z,a,b+1,c);
        cnt+=dp[x][y][z][a][b+1][c];
        tot++;
    }
    if(c<4)
    {
        if(dp[x][y][z][a][b][c+1]==-1) dfs(x,y,z,a,b,c+1);
        cnt+=dp[x][y][z][a][b][c+1];
        tot++;
    }
    if(num%2==0)
    {
        if(cnt>0) dp[x][y][z][a][b][c]=1;
        else dp[x][y][z][a][b][c]=0;
    }
    else
    {
        if(cnt == tot) dp[x][y][z][a][b][c]=1;
        else dp[x][y][z][a][b][c]=0;
    }
}

int main()
{
    memset(dp, -1, sizeof(dp));
    for(int x=0; x<=4; x++)
    {
        for(int y=0; y<=4; y++)
        {
            for(int z=0; z<=4; z++)
            {
                for(int a=0; a<=4; a++)
                {
                    for(int b=0; b<=4; b++)
                    {
                        for(int c=0; c<=4; c++)
                        {
                            int num=a+b+c+x+y+z;
                            int sum=x+2*y+3*z+4*a+5*b+6*c;
                            if(sum>31)
                            {
                                if(num%2==0)
                                    dp[x][y][z][a][b][c]=1;
                                else
                                    dp[x][y][z][a][b][c]=0;
                            }
                        }
                    }
                }
            }
        }
    }
    dfs(0, 0, 0, 0, 0, 0);
    int tmp[7];
    char s[233];
    while (cin >> s) {
        int n = strlen (s);
        memset(tmp, 0, sizeof(tmp));
        for (int i = 0; i < n; i++) {
            tmp[s[i]-'0']++;
        }
        int ans = dp[tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]][tmp[6]];
        printf ("%s %s\n", s, ans ? "A" : "B");
    }
}