表示考场上有考虑过状压的，后来因为忘了太多期望 DP 的知识没写出来（
首先把 \(p_i=0\) 的物品缩起来，这样考虑剩下的物品就行了，计算的时候顺便加入这些物品的贡献即可。
实际上此题的 DP 非常不好写，考虑记搜每个物品已经用了多少次的情况下，能得到的最大期望。
我们需要一种哈希方式，当然也很简单，在一个二进制数里给每个物品留 \(\lfloor\log_2 p_i \rfloor + 1\) 个二进制位存就可以了（实际上直接留 \(p_i\) 个位也是极好的）。
那么转移时实际上考虑此时抽到这个物品放弃与否即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
const int N = 1e5;
const int M = 21;
const double eps = 1e-5;
int n,m;
struct note
{
int p,v;
inline bool operator<(const note &o) const
{
return p > o.p;
}
} a[N + 5];
int c[M + 5];
double f[(1 << M) + 5];
long long sum;
inline int Hash()
{
int ret = 1;
for(register int i = 1;i <= m;++i)
ret = (ret << a[i].p) + c[i];
return ret;
}
double calc()
{
int w = Hash();
if(fabs(f[w]) > eps)
return f[w];
double ret = sum;
for(register int i = 1;i <= m;++i)
c[i] < a[i].p ? (++c[i],ret += max((double)a[i].v,calc()),--c[i]) : (ret += a[i].v);
ret /= n;
return f[w] = ret;
}
int main()
{
freopen("seed.in","r",stdin),freopen("seed.out","w",stdout);
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d%d",&a[i].p,&a[i].v),!a[i].p && (sum += a[i].v);
sort(a + 1,a + n + 1);
for(m = 0;a[m + 1].p;++m);
printf("%.4f\n",calc());
}