首页 > 代码库 > uva 1637 Double Patience
uva 1637 Double Patience
https://vjudge.net/problem/UVA-1637
36张牌分成9堆,每堆4张牌。每次可以拿走某两堆顶部的牌,但需要点数相同。
如果有多种拿法则等概率的随机拿。
如果最后拿完所有牌则游戏成功。按顺序给出每堆牌的4张牌,求成功概率。
#include<cstdio>using namespace std;char s[10][5];char ss[5];int left[10];int v[2000001];double dp[2000001];int t;int state(){ int tmp=0; for(int i=1;i<=9;i++) tmp=tmp*5+left[i]; return tmp; }double solve(){ int x=state(); if(!x) return 1.0; if(v[x]==t) return dp[x]; double ans=0; int cnt=0; for(int i=1;i<9;i++) for(int j=i+1;j<=9;j++) if(left[i]&&left[j]&&s[i][left[i]]==s[j][left[j]]) { left[i]--; left[j]--; ans+=solve(); cnt++; left[i]++; left[j]++; } if(cnt) dp[x]=1.0*ans/cnt; else dp[x]=0; v[x]=t; return dp[x];}int main(){ while(scanf("%s",ss)!=EOF) { s[1][1]=ss[0]; for(int j=2;j<=4;j++) { scanf("%s",ss); s[1][j]=ss[0]; } for(int i=2;i<=9;i++) for(int j=1;j<=4;j++) { scanf("%s",ss); s[i][j]=ss[0]; } t++; for(int i=1;i<=9;i++) left[i]=4; printf("%.6lf\n",solve()); }}
uva 1637 Double Patience
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。