首页 > 代码库 > HDU_5602_概率dp

HDU_5602_概率dp

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

 

dp[1][i][j]表示轮到第二个人操作时,第一人总和i,第二人总和j,第一人胜的最小概率(因为每个人都是聪明的,所以选最小)。

dp[0][i][j]表示第一个人操作时,第一个人胜的最大概率。

先算dp[1],然后用dp[1]算dp[0],注意x==y的情况。

 

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int vis[2][35][35] = {0};double dp[2][35][35];char a[5];int cal(char c){    switch(c)    {        case A:   return 1;        case T:        case J:        case K:        case Q:   return 10;        default:    return c-0;    }}double dfs1(int x,int y){    if(y > 21)  return 1;    if(vis[1][x][y])    return dp[1][x][y];    double temp = 0;    dp[1][x][y] = x>y;    for(int i = 1;i < 10;i++)   temp += dfs1(x,y+i)/13;    temp += dfs1(x,y+10)*4/13;    dp[1][x][y] = min(dp[1][x][y],temp);    vis[1][x][y] = 1;    return dp[1][x][y];}double dfs0(int x,int y){    if(x > 21)  return 0;    if(vis[0][x][y])    return dp[0][x][y];    dp[0][x][y] = dfs1(x,y);    double temp = 0;    for(int i = 1;i < 10;i++)    temp += dfs0(x+i,y)/13;    temp += dfs0(x+10,y)*4/13;    dp[0][x][y] = max(dp[0][x][y],temp);    vis[0][x][y] = 1;    return dp[0][x][y];}int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%s",a);        int first = 0,second = 0;        first += cal(a[0]);        first += cal(a[1]);        second += cal(a[2]);        second += cal(a[3]);        double ans = dfs0(first,second);        if(ans > 0.5)   printf("YES\n");        else    printf("NO\n");    }    return 0;}

 

HDU_5602_概率dp