hdu_5602 Black Jack

题目:

  21 point,also named Black Jack, originated in France,has spread around the world.
  21 point, a gambling game played by using poker,is also the only one which is able to win banker by using probability calculation.
  --- Encyclopedia from good search
  We define blackjack rules are as follows, which is different from the original rules slightly.
  cards are as follows:
  A 2 3 4 5 6 7 8 9 10 J Q K
  A is as 1 point.
  JQK are all as 10 points.
  We assume that the casino prepared a lot of cards,that is, you can assume that the probability of getting each card is the same.
  There are two players who were banker and Player.
  They get two cards at first and can see the card each other.
  Player operates first.
  Every turn, he can bid or stop bidding.
  If he bid, he can take a card from the deck.
  Once the the points are over 21,he will lose at once,which is called "busting", otherwise he will bid until stopping bidding and turn to banker. the rule of banker is the same as the player's.
  If there is no "busting", the one who have higher points win.
  If they have the same points,they get the tie.
  Here is the task,we give you the cards that both people have gotten.
  please judge whether the Player have more than 50% winning percentage, if yes, output "YES", otherwise output,"NO".
  Oh, yes, everyone is very smart.

思路:

  代表玩家有点,庄主有点时,0代表轮到玩家,1代表庄主时,玩家赢的概率。
  每次就只需要在抽和不抽两个中做出一个选择,因为两人都足够聪明,所以玩家要让自己赢的概率最大,庄主要让概率最小,那么dp方程也很明显了(见代码)。

代码:

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##__END__=(b);i<=i##__END__;i++)
#define DOR(i,a,b) for(int i=(a),i##__END__=(b);i>=i##__END__;i--)
#define get(x) ((x)?1.0:0.0)
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
double dp[2][25][25];
bool vis[2][25][25];
double solve(int x,int y,int d){
    if(vis[d][x][y])return dp[d][x][y];
    if(x>21)return 0;
    if(y>21)return 1;
    double ans=0.0;
    if(!d){
        FOR(i,1,9)
            ans+=solve(x+i,y,d)/13;
        ans+=solve(x+10,y,d)*4/13;
        tomax(ans,solve(x,y,1));
    }
    else {
        FOR(i,1,9)
            ans+=solve(x,y+i,d)/13;
        ans+=solve(x,y+10,d)*4/13;
        tomin(ans,get(x>y));
    }
    return vis[d][x][y]=1,dp[d][x][y]=ans;
}
int tonum(char c){
    if(c=='A')return 1;
    if(isdigit(c))return c-'0';
    return 10;
}
int main(){
    int T;
    char s[10];
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        puts(solve(tonum(s[0])+tonum(s[1]),tonum(s[2])+tonum(s[3]),0)>0.5?"YES":"NO");
    }
    return 0;
}