题目描述：

六一儿童节到了,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 64 63 70

样例输出：

1 0.172 0.173 0.1713 0.1114 0.1115 0.1112 0.1110 0.1011 0.10 DP的背包问题。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 using namespace std; 7  8 struct Node 9 {10     double p;11     int val;12     Node(){}13     Node(int v, double _p):val(v), p(_p){}14 };15 16 bool comp(const Node &lhs, const Node &rhs)17 {18     if (lhs.p > rhs.p)19         return true;20     else if (lhs.p < rhs.p)21         return false;22     else23         return lhs.val < rhs.val;24 }25 26 int main()27 {28     int n, m;29     int f[10][81];30     while(cin >> n)31     {32         if (n == 0)33             break;34         cin >> m;35         memset(f, 0, sizeof(f));36 37         for(int i = 1; i <= m; i++)38             f[0][i] = 1;39 40         int v = m * n;41         for(int i = 1; i < n; i++)42             for(int j = 1; j <= m; j++)43                 for(int k = 1; k <= v - j; k++)44                     f[i][k+j] += f[i-1][k];45 46         vector
            
              num;47 int sum = 0;48 for(int i = 1; i <= v; i++)49 sum += f[n-1][i];50 51 for(int i = 1; i <= v; i++)52 {53 double p = f[n-1][i] / (double)sum;54 p += 0.005;55 int a = (int)(p * 100);56 p = (double)a / 100;57 num.push_back(Node(i, p));58 }59 60 sort(num.begin(), num.end(), comp);61 62 for(int i = 0; i < 3; i++)63 printf("%d %.2lf\n", num[i].val, num[i].p);64 printf("\n");65 }66 }