首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。