CodeForces - 262D:Maxim and Restaurant（期望DP）

以你之姓@ 2021-10-25 13:50 352阅读 0赞

**Discription**  
Maxim has opened his own restaurant! The restaurant has got a huge table, the table’s length is p meters.

Maxim has got a dinner party tonight, n guests will come to him. Let’s index the guests of Maxim’s restaurant from 1 to n. Maxim knows the sizes of all guests that are going to come to him. The i-th guest’s size (ai) represents the number of meters the guest is going to take up if he sits at the restaurant table.

Long before the dinner, the guests line up in a queue in front of the restaurant in some order. Then Maxim lets the guests in, one by one. Maxim stops letting the guests in when there is no place at the restaurant table for another guest in the queue. There is no place at the restaurant table for another guest in the queue, if the sum of sizes of all guests in the restaurant plus the size of this guest from the queue is larger than p. In this case, not to offend the guest who has no place at the table, Maxim doesn’t let any other guest in the restaurant, even if one of the following guests in the queue would have fit in at the table.

Maxim is now wondering, what is the average number of visitors who have come to the restaurant for all possible n! orders of guests in the queue. Help Maxim, calculate this number.

**Input**  
The first line contains integer n (1 ≤ n ≤ 50) — the number of guests in the restaurant. The next line contains integers a1, a2, …, an (1 ≤ ai ≤ 50) — the guests’ sizes in meters. The third line contains integer p (1 ≤ p ≤ 50) — the table’s length in meters.

The numbers in the lines are separated by single spaces.

**Output**  
In a single line print a real number — the answer to the problem. The answer will be considered correct, if the absolute or relative error doesn’t exceed 10 - 4.

**Examples**  
Input

3
    1 2 3
    3

Output

1.3333333333

**Note**  
In the first sample the people will come in the following orders:

(1, 2, 3) — there will be two people in the restaurant;  
(1, 3, 2) — there will be one person in the restaurant;  
(2, 1, 3) — there will be two people in the restaurant;  
(2, 3, 1) — there will be one person in the restaurant;  
(3, 1, 2) — there will be one person in the restaurant;  
(3, 2, 1) — there will be one person in the restaurant.  
In total we get (2 + 1 + 2 + 1 + 1 + 1) / 6 = 8 / 6 = 1.(3).

**题意**  
给n个人，以及每个人占据桌子的长度，给一个长度m的桌子。  
让n个人排队，依次进入桌子就坐，每个人占一定空间。如果剩余空间不能让下一个人进入，那么不再让后面的人进入。  
这n个人有n!种排队方式，求在不同的排序情况下桌子坐下的人数的期望。

**思路**  
自己没做出来，看考了网上大佬的代码。  
`dp[i][j][k]`表示的是前i个人，进去`j`个人，所占空间为`k`的种类数；因为进去了`j`个人，所以一定有`n-j`个人进不去，所以进去的人乘`j`的阶乘，进不去的人乘`n-j`的阶乘，即为在此种情况下的人数。  
求和除以n的阶乘就是平均人数。  
详见代码。

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    int n,m;
    long double ans;
    int a[60];
    long double dp[60][60][110];///dp[i][j][k]表示的是前i个人，进去j个人，所占空间为k的种类数
    long double f[60];///f[i]表示i的阶乘
    int main()
    {
        cin>>n;
        f[0]=1;
        for(int i=1; i<=n; i++)
            f[i]=f[i-1]*i;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        cin>>m;
        sort(a+1,a+1+n);
        dp[1][0][0]=1;///数组a中前1个人,进去0个人，所占空间为0,有一种方法
        dp[1][1][a[1]]=1;///数组a中前1个人，进去1个人，所占空间为a[1]，有一种方法
        for(int i=2; i<=n; i++)
        {
            for(int j=0; j<=i; j++)
            {
                for(int k=0; k<=m; k++)
                {
                    dp[i][j][k]+=dp[i-1][j-1][k-a[i]];///第i个人进去，此时有j个人，所占空间为j
                    dp[i][j][k]+=dp[i-1][j][k];///第i个人不进去
                }
            }
        }
        for(int j=1; j<=n; j++)
        {
            for(int k=0; k<=m; k++)
                ans+=dp[n][j][k]*(f[j]*f[n-j]);///进去j个人，乘j的阶乘，n-j个人一定不能进去，乘n-j的阶乘
        }
        ans=ans/f[n];///除以种类数n的阶乘即为期望值
        cout<<ans<<endl;
        return 0;
    }