UVA – 1637 – Double Patience (概率计算)

2018年2月20日 0 条评论 4 次阅读 0 人点赞

题目链接:

UVA - 1637

题目大意:

一共有9堆牌,每堆牌四张。每次可以取堆顶点数相同的两张牌,如果有多种方案则选取是随机的。

如果最后将所有牌取完,则视为游戏胜利,求胜利的概率。

题目分析:

概率计算,利用递推的方法计算出最终的概率,注意去重。

给出代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <list>
#include <cstdio>
#include <map>
#include <set>
#include <string>
using namespace std;
char card[10][10][10];
map<vector<int>,double> d;
double solve(vector<int> &temps,int cnt)
{
    if(cnt==0)
        return 1;
    else
    {
        if(d.count(temps)!=0)
            return d[temps];
        double sum=0;
        double tot=0;
        for(int i=1;i<=9;i++)
        {
            if(temps[i]>0)
            for(int j=i+1;j<=9;j++)
            {
                if(temps[j]>0)
                if(card[i][temps[i]][0]==card[j][temps[j]][0])
                {
                    temps[i]--;
                    temps[j]--;
                    tot++;
                    sum+=solve(temps,cnt-2);
                    temps[i]++;
                    temps[j]++;
                }
            }
        }
        if(sum==0)
            return d[temps]=0;
        else
            return d[temps]=sum/tot;
    }
}
int main()
{
    //  ios::sync_with_stdio(false);
    while(scanf("%s%s%s%s",card[1][1],card[1][2],card[1][3],card[1][4])!=EOF)
    {
        vector<int> temps;
        d.clear();
        for(int i=2;i<=9;i++)
        {
            for(int j=1;j<=4;j++)
            {
                scanf("%s",card[i][j]);
            }
        }
        temps.clear();
        for(int i=0;i<=9;i++)
        {
            temps.push_back(4);
        }
        double ans=solve(temps,36);
        printf("%.6lf\n",ans);
    }
    return 0;
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(0)