Black Jack

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5602

记忆化搜索

用dp[0][i][j]记录当player为i，banker为j时player赢的概率；dp[1][i][j]记录当player为i，banker为j时banker输或平局的概率。

显然，player当前的决策只有两种：1.continue继续拿牌；2.turn to banker让庄家拿牌.

故dp[0][i][j]=max(继续拿牌玩家赢的概率，让庄家拿牌庄家输或平局的概率)；

而继续拿牌玩家赢的概率=1/13*dp[0][i+1...i+9][j]+4/13*dp[0][i+10][j],

让庄家拿牌庄家输或平局的概率=1/13*dp[1][i][j+1...j+9]+4/13*dp[1][i][j+10].

值得注意的是，玩家和庄家拿牌的策略有所不同：庄家只要当前牌数比玩家大或相等，庄家即可不再拿牌.

不说了，要落泪了，回去补复变了。

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define Max(x,y) (x>y?x:y)
 4 using namespace std;
 5 int T,play,bank;
 6 char s[5];
 7 double dp[2][25][25],flag;//0.player win's gay 1.banker lose's gay
 8 bool mark[2][25][25];
 9 int hs(char c){
10     if(c=='A')return 1;
11     else if('1'<=c&&c<='9')return c-'0';
12     return 10;
13 }
14 void init(){
15     scanf("%s",s);
16     play=hs(s[0])+hs(s[1]);
17     bank=hs(s[2])+hs(s[3]);
18 }
19 double dfsForBank(int p,int b){
20     if(b>21)return 1.0;
21     if(b>=p)return 0.0;
22     if(mark[1][p][b])return dp[1][p][b];
23     mark[1][p][b]=1;
24     for(int i=1;i<=10;++i){
25         if(i!=10)dp[1][p][b]+=1.0/13*dfsForBank(p,b+i);
26         else dp[1][p][b]+=4.0/13*dfsForBank(p,b+i);
27     }
28     return dp[1][p][b];
29 }
30 double dfsForPlay(int p,int b){
31     if(p>21)return 0.0;
32     if(mark[0][p][b])return dp[0][p][b];
33     mark[0][p][b]=1;
34     double turnOver=dfsForBank(p,b);//turn to banker
35     for(int i=1;i<=10;++i){//continue
36         if(i!=10)dp[0][p][b]+=1.0/13*dfsForPlay(p+i,b);
37         else dp[0][p][b]+=4.0/13*dfsForPlay(p+i,b);
38     }
39     dp[0][p][b]=Max(dp[0][p][b],turnOver);
40     return dp[0][p][b];
41 }
42 int main(void){
43     scanf("%d",&T);
44     while(T--){
45         init();
46         flag=dfsForPlay(play,bank);
47         if(flag>0.5)printf("YES
");
48         else printf("NO
");
49     }
50 }