当前位置：首页 > news >正文

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

news 来源：原创 2024/5/2 15:39:57

题目链接

想了挺久，枚举每一件物品，当做关键物品，假设再加这一件物品，就>=c了，把剩下的物品背一下包，dp[i][j]表示i个物品可以组成重量j的个数。

这样就可以知道前面放i件，后边肯定放n-i-1件，乱搞搞，算double，边乘边算保证不要越界。最后注意，LL和sum <= c的时候情况。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 #define LL __int64
 9 LL dp[2][51][101];
10 int p[51];
11 int main()
12 {
13     int i,j,k,u,v,n,c,s1,s2,sum;
14     double ans = 0;
15     scanf("%d",&n);
16     sum = 0;
17     for(i = 1; i <= n; i ++)
18     {
19         scanf("%d",&p[i]);
20         sum += p[i];
21     }
22     scanf("%d",&c);
23     if(sum <= c)
24     {
25         printf("%d\n",n);
26         return 0;
27     }
28     for(i = 1; i <= n; i ++)
29     {
30         memset(dp,0,sizeof(dp));
31         dp[0][0][0] = 1;
32         s1 = 0;
33         s2 = 1;
34         for(j = 1; j <= n; j ++)
35         {
36             if(i == j) continue;
37             for(k = 0; k < j; k ++)
38             {
39                 for(u = 0; u <= 100; u ++)
40                     dp[s2][k][u] = dp[s1][k][u];
41             }
42             for(k = 0; k < j; k ++)
43             {
44                 for(u = 0; u < 100; u ++)
45                 {
46                     if(dp[s1][k][u])
47                     {
48                         if(u+p[j] <= 100)
49                             dp[s2][k+1][u+p[j]] += dp[s1][k][u];
50                     }
51                 }
52             }
53             swap(s1,s2);
54         }
55         for(j = 0; j < c; j ++)
56         {
57             if(j + p[i] >= c)
58             {
59                 for(k = 0; k < n; k ++)
60                 {
61                     if(dp[s1][k][j] == 0) continue;
62                     double temp = dp[s1][k][j];
63                     for(u = 1,v = k+1;u <= n-k-1;u ++,v++)
64                     temp *= u*1.0/v;
65                     temp /= n;
66                     if(j + p[i] == c)
67                     ans += temp*(k+1);
68                     else
69                     ans += temp*k;
70                 }
71             }
72         }
73     }
74     printf("%lf\n",ans);
75     return 0;
76 }