Black Jack

? ?Accepts: 0 ? ?Submissions: 61 ?Time Limit: 2000/1000 MS (Java/Others) ? ?Memory Limit: 65536/65536 K (Java/Others) 問題描述 21點又名黑杰克（英文：Blackjack），起源于法國，已流傳到世界各地。 21點，是一種使用撲克牌玩的賭博游戲。亦是唯一一種在賭埸中可以在概率中戰勝莊家的一種賭博游戲。 ———來自好搜百科 我們定義21點的規則如下，和原始規則稍微不一樣。 牌點數如下： A 2 3 4 5 6 7 8 9 10 J Q K A當成1點 JQK全部當成10點。 我們假設賭場準備了很多副牌，也就是可以假設每次摸到每張牌的概率是一樣的。 玩家有兩個人，分別為莊家和閑家。 一開始兩人都拿兩張牌，兩個人都可以看到對方的牌。 閑家先操作，每次可以叫牌或者停止叫牌。 如果叫牌，從牌堆中拿一張牌，一旦叫牌后手牌超過21點，直接判輸，稱為“爆點”，否則一直叫牌直到停止叫牌，輪到莊家。 輪到莊家后，跟閑家一樣的叫牌或停止叫牌，一旦爆點也是直接判輸。 如果沒有爆點，誰點數大就誰贏，點數一樣判平。 給你兩家的牌，如果閑家勝率>50%輸出"YES"，否則輸出"NO" 哦，對了，每個人都是絕頂聰明的。 輸入描述 第一行一個數Test(Test<=100000)。表示數據組數。 下面每組數據，一個4字符字符串,前兩個字符表示閑家的牌，后兩張表示莊家的。 （用T表示10） 輸出描述 對于每組數據輸出"YES"或者"NO",表示閑家是否有50%以上的勝率。 輸入樣例 1 TTT9 輸出樣例 YES //很明顯閑家并不會叫牌，莊家只有2/13的機會贏。

dp1[a][b]表示閑家和莊家點數分別為a和b時閑家叫牌時閑家的勝率，dp2[a][b]表示閑家和莊家點數分別為a和b時莊家叫牌時閑家的勝率。
答案為dp1(a,b)>0.5。 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll; const int maxn=31; const int INF=1<<29; const double EPS=0.0000000001;char s[maxn]; int n; int a,b; double dp1[maxn][maxn]; double dp2[maxn][maxn];int shu(char x) {if(x=='A') return 1;if(x=='T'||x=='J'||x=='K'||x=='Q') return 10;return x-'0'; }double dfs2(int a,int b) {double &res=dp2[a][b];if(res>-EPS) return res;if(a<=b) return res=0;res=0;REP(i,1,9){if(b+i<=21) res+=dfs2(a,b+i)/13;else res+=1.0/13;}REP(i,1,4){if(b+10<=21) res+=dfs2(a,b+10)/13;else res+=1.0/13;}return res; }double dfs1(int a,int b) {double &res=dp1[a][b];if(res>-EPS) return res;res=0;REP(i,1,9) if(a+i<=21) res+=dfs1(a+i,b)/13;REP(i,1,4) if(a+10<=21) res+=dfs1(a+10,b)/13;res=max(dfs2(a,b),res);return res; }int main() {freopen("in.txt","r",stdin);int T;cin>>T;while(T--){scanf("%s",s);a=shu(s[0])+shu(s[1]);b=shu(s[2])+shu(s[3]);REP(i,1,maxn-1) REP(j,1,maxn-1) dp1[i][j]=dp2[i][j]=-1.0;puts(dfs1(a,b)>0.5+EPS?"YES":"NO");}return 0; } View Code

?

轉載于:https://www.cnblogs.com/--560/p/5079365.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的bestcoder #67 div2 1003 Black Jack 概率dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。