JZOJ 6509 Seed

发表于 | 分类于 |

表示考场上有考虑过状压的，后来因为忘了太多期望 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
#include <cstdio>
#include <cmath>
#include <algorithm>
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());
}