#include<stdio.h>

double dp[][],dp0[];

int main(){

    int i,n,j,k;

    while(scanf("%d",&n)!=EOF){

        int n6=n*;

        for(i=;i<=;i++){

            for(j=;j<=n6;j++){

                dp[i][j]=;

            }

        }

        i=;

        for(j=;j<=;j++){

            dp[i][j]=/6.0;

            dp0[j]=/6.0;

        }

        for(i=;i<=n;i++){

            int first=i-,end=(i-)*;

            for(j=first;j<=end;j++){

                for(k=;k<=;k++){

                    dp[i%][j+k]=;

                }

            }

            for(j=first;j<=end;j++){

                for(k=;k<=;k++){

                    dp[i%][j+k]+=dp[(i-)%][j]*dp0[k];

                }

            }

        }

        int first=n,end=n*;

        for(i=first;i<=end;i++){

            printf("%d: %.3lf\n",i,dp[n%][i]);

        }

    }

    return ;

}

时间限制：2 秒

内存限制：32 兆

特殊判题：否

提交：357

解决：107

题目描述：

六一儿童节到了,YZ买了很多丰厚的礼品,准备奖励给JOBDU里辛劳的员工。为了增添一点趣味性,他还准备了一些不同类型的骰子,打算以掷骰子猜数字的方式发放奖品。例如,有的骰子有6个点数(点数分别为1~6),有的骰子有7个(点数分别为1~7),还有一些是8个点数(点数分别为1~8) 。他每次从中拿出n个同一类型的骰子(假设它们都是拥有m个点数并且出现概率相同)投掷,然后让员工在纸上按优先级(从高到低)的顺序写下3个数上交,表示他们认为这些骰子最有可能的点数之和是多少。第一个数就猜对的人,是一等奖;第二个数才猜对的人是二等奖;如果三个数都不是正确答案,别灰心！YZ还准备了很多棒棒糖。ZL很聪明,他想了想,打算把概率(以保留两位小数的概率计)最高的三个数找出来,如果有概率相同,则选择其中点数和最小的那个数。你觉得ZL会依次写下哪三个数？

输入：

输入有多组数据。

每组数据一行,包含2个整数n(0<=n<=10),m(6<=m<=8),n表示YZ拿出的骰子数,m表示骰子拥有的点数。如果n=0,则结束输入。

输出：

对应每组数据,输出ZL最可能依次写下的点数,以及其对应的概率值。概率值按4舍5入要求保留2位小数。每组数据之间空一行,注意:最后一组数据末尾无空行。

样例输入：

1 6

4 6

3 7

0

样例输出：

1 0.17

2 0.17

3 0.17

13 0.11

14 0.11

15 0.11

12 0.11

10 0.10

11 0.10

#include<stdio.h>

#include<iostream>

#include<algorithm>

using namespace std;

double dp[][];

struct data{

    int no;

    double v;

}s[];

int cmp(data x,data y){

    if(x.v==y.v)return x.no<y.no;

    else return x.v>y.v;

}

int main(){

    int i,n,j,k,m;

    while(scanf("%d",&n)!=EOF&&n){

        scanf("%d",&m);

        int nm=n*m;

        for(i=;i<=n;i++){

            for(j=;j<=nm;j++){

                dp[i][j]=;

            }

        }

        i=;

        for(j=;j<=m;j++){

            dp[i][j]=1.0/m;

        }

        for(i=;i<=n;i++){

            int first=i-,end=(i-)*m;

            for(j=first;j<=end;j++){

                for(k=;k<=m;k++){

                    dp[i][j+k]+=dp[(i-)][j]*dp[][k];

                }

            }

        }

        int first=n,end=n*m;

        for(i=first;i<=end;i++){

            s[i].no=i;

            s[i].v=((int)((dp[n][i]+0.005)*));

        }

        sort(&s[first],&s[end+],cmp);

        for(i=first;i<=first+;i++){

            printf("%d %.2lf\n",s[i].no,s[i].v/100.0);

        }printf("\n");

    }

    return ;

}