Codeforces Round #160 (Div. 2) D. Maxim and Restaurant(DP)

时间:2023-01-21 14:58:55

这题纠结好久了 看一神代码 想了N久才明白它的意思 

dp[i][j]表示放了i个数后和为J的方式有多少种

而在算阶层总数的时候 会重一部分 而重的那一部分恰好为小于等于P的长度 所以就直接省了乘长度这一部分

Codeforces Round #160 (Div. 2) D. Maxim and Restaurant(DP)Codeforces Round #160 (Div. 2) D. Maxim and Restaurant(DP)
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 using namespace std;
 8 #define LL long long
 9 int a[55];
10 LL dp[55][55];
11 double pp[55];
12 int main()
13 {
14     int i,j,k,n,p;
15     scanf("%d",&n);
16     for(i = 1; i <= n ; i++)
17     scanf("%d",&a[i]);
18     scanf("%d",&p);
19     dp[0][0] = 1;
20     for(i = 1; i <= n ;i++)
21         for(j = n ; j>=1 ; j--)
22         for(k = p ; k >= a[i] ; k--)
23         {
24             dp[j][k] += dp[j-1][k-a[i]];
25         }
26     pp[0] = 1;
27     for(i = 1; i <= n ;i++)
28     pp[i] = pp[i-1]*i;
29     double ans=0;
30     for(i = 0 ;i <= n ; i++)
31     {
32         for(j = 1 ; j <= p ; j++)
33         {
34             ans+=pp[i]*pp[n-i]*dp[i][j];
35         }
36     }
37     printf("%.8lf\n",ans/pp[n]);
38     return 0;
39 }
View Code