首页 > 代码库 > uva 1637 Double Patience

uva 1637 Double Patience

2024-09-30 07:22:39   216人阅读

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


联系
我们