Black Jack

题目链接：

记忆化搜索

用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
     
       2 #include
      
        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 banker35     for(int i=1;i<=10;++i){
   //continue36         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\n");48         else printf("NO\n");49     }50 }