NO IMAGE

傳送門:
http://acm.hdu.edu.cn/showproblem.php?pid=5602

題意:
21點遊戲,A當成1,JQK全部當成10點,輪流叫牌,爆點直接判輸,假設牌數特別多,且每個人拿到每張牌的概率是一樣的!!
一開始二者都有張牌為輸入!問最後閒家勝率大於50%的概率!!!!!! 

明顯的概率dp,用記憶化搜搜去寫嘛!!!
兩個dfs分別模擬閒家和莊家叫牌時的情況,終止條件是莊家叫牌,用dp[i,j]表示閒家現有牌定數和為i,莊家為j,時獲勝的概率,那麼顯然就有
dp[i,j] =1/13*dp[i (1~9),j] 4/13*dp[10~K,j]
那麼對於莊家而言,如果當前i<=j那麼dp值直接為0,否則j要繼續往上加,然後就是正常的去判斷一下就ok了!!!

這題很邪門,寫的時候各種亂,最後還因為初始化的時候直接1到maxn wrong了,真應該注意這一點,注意本題應該開兩個dp陣列,分別表示該誰取得時候獲勝的概率,如果要是隻開一個的話,因為莊家在暫時失敗的時候是可以繼續取獲勝的,而開一個陣列地話則不能實現這一點!!!

哦哦,原來是我考慮錯了,我之前想的是
dfs2應該有2種終止狀態,但實際上只有1種,即a<=b的話,res就為0;否則的話,肯定要繼續取。。。。是等於1收尾的時候想錯了,等於1的情況只有是當目前a>b,然後現在應該b繼續取但是取爆點了的情況,對對,就是這樣去想的,只有這一種情況才能導致閒家最後獲勝,這也提醒了我一點,在思考問題的時候,就應該順著一個人的角度去想,否則的話很容易就想亂了,最後導致各種邏輯錯誤

還有應該注意的就是,這種dp兩個狀態一定要開兩份,分別表示當前是誰來取,獲勝的概率,否則是記錄不下來的!!!!

本題還有應該注意的的地方就是,概率初始化的時候應該取為-1,概率有可能為0,這種狀態因為已經計算過了,所以一定要記錄下來,所以說初始化應該為-1,然後判斷條件是>-eps!!!!

注意是一直叫牌直到停牌,即不是選擇叫還是不叫,如果當前還是暫時輸,可以一直叫下去,所以這樣遞迴寫就非常合情合理了!!!

code:

#include<bits/stdc  .h>
using namespace std;
int t;char s[100];int sum1,sum2;
const int maxn=33;
const double eps=1e-8;
double dp1[maxn][maxn],dp2[maxn][maxn];
int get(char s){
if(s=='A') return 1;
if(s=='T'||s=='J'||s=='Q'||s=='K') return 10;
return s-'0';
}
double dfs2(int a,int b){
double &res=dp2[a][b];
if(res>-eps) return res;
if(a<=b) return res=0.0;
//  if(a>b||b>21) return res=1.0;
res=0.0;
for(int i=1;i<=9;i  ){
if(b i<=21)
res =(dfs2(a,b i)/13);
else res =1.0/13;
}
for(int i=1;i<=4;i  ){
if(b 10<=21)
res =(dfs2(a,b 10)/13);
else res =1.0/13;
}
return res;
}
double dfs(int a,int b){
double &res=dp1[a][b];
if(res>-eps) return res;
if(a>21) return res=0.0;
res=0.0;
for(int i=1;i<=9;i  ){
res =(dfs(a i,b)/13);
}
for(int i=1;i<=4;i  ){
res =(dfs(a 10,b)/13);
}
res=max(res,dfs2(a,b));
return res;
}
int main(){     
scanf("%d",&t);
while(t--){
scanf("%s",s);sum1=0;sum2=0;
sum1=get(s[0]) get(s[1]);
sum2=get(s[2]) get(s[3]);
for(int i=1;i<maxn;i  ){
for(int j=1;j<maxn;j  ){
dp1[i][j]=-1.0;dp2[i][j]=-1.0;
}
}
if(dfs(sum1,sum2)-0.5>eps) puts("YES");
else puts("NO");
}
return 0;
}