Light oj 1064 Throwing Dice (概率dp)

题意：给定n个骰子和一个x，要求出用这些骰子投出大于等于x的概率。要求最简。

分析：先预处理算出i个骰子得到的和为j的种数。然后用gcd函数约分。

dp[i+1][j+k]=sigma(dp[i][j]) (1<=k<=6)

AC代码1：

#include<cstdio>
#include<iostream>
#include<cstring>
typedef unsigned long long ull;

using namespace std;

__int64 dp[30][155];

__int64 gcd(__int64 x,__int64 y)
{
    return y?gcd(y,x%y):x;
}

int main()
{
    __int64 up,down,g;
    int T,n,x,i,j,k;
    for(i=1;i<=6;i++)
        dp[1][i]=1;
    for(i=1;i<25;i++)
    {
        for(j=i;j<=6*i;j++)
        {
            for(k=1;k<=6;k++)
                dp[i+1][j+k]+=dp[i][j];
        }
    }
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        scanf("%d%d",&n,&x);
        if(x>n*6)
        {
            printf("Case %d: 0\n",cas);
            continue;
        }
        if(x<=n)
        {
            printf("Case %d: 1\n",cas);
            continue;
        }
        up=0,down=1;
        for(i=x;i<=n*6;i++)
            up+=dp[n][i];
        for(j=0;j<n;j++) down*=6;
        g=gcd(up,down);
        printf("Case %d: %lld/%lld\n",cas,up/g,down/g);
    }
    return 0;
}

AC代码2：

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

__int64 dp[25][155];

__int64 gcd(__int64 x,__int64 y)
{
    return y?gcd(y,x%y):x;
}

int main()
{
    __int64 up,down,g;
    int T,n,x;
    for (int i = 1; i <= 24; i ++)
		for (int j = 1; j <= 150; j ++) {
			if (i == 1 && j <= 6)
				dp[i][j] = 1;
			for (int k = 1; k <= 6; k ++) {
				if (j >= k)
					dp[i][j] += dp[i - 1][j - k];
			}
		}
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        scanf("%d%d",&n,&x);
        up=0,down=0;
        for(int i=n;i<=n*6;i++)
        {
            down+=dp[n][i];
            if(x<=i)
                up+=dp[n][i];
        }
        if(up==down)
            printf("Case %d: 1\n",cas);
        else if(up==0)
            printf("Case %d: 0\n",cas);
        else
        {
            g=gcd(up,down);
            printf("Case %d: %lld/%lld\n",cas,up/g,down/g);
        }
    }
    return 0;
}

Light oj 1064 Throwing Dice (概率dp)

原文：http://blog.csdn.net/u012841845/article/details/18866545