GZY的博客

BZOJ4374 Little Elephant and Boxes 题解

 题解  706  

注意到「物品数」和「可能获得的钻石数」很小，以这两个为切入点考虑。

首先通过一个背包DP，求出有 $i$ 个钻石，获得 $j$ 个物品所花费的最小钱数 $f(i,j)$，注意这 $i$ 个钻石不需要全用完。

然后假设小象有 $i$ 个钻石，想要最多取得 $j$ 个物品，那么他所拥有的钱数的范围是 $\left [ f_{i,j},f_{i,j+1} \right ) $，如果他拥有了不少于 $f_{i,j+1}$ 的钱，只买 $j$ 个物品的方案就不是物品最多的方案了。

我们希望求出小象在所有可能获得的钻石和钱数的方案中，找到所有钻石数为 $i$，钱数属于 $\left [ f_{i,j},f_{i,j+1} \right ) $ 的情况的概率之和，将这个概率 $p$ 乘以物品数 $j$ 就是期望。

如何求这个概率之和，注意到箱子的个数最多为 $30$ ，考虑折半搜索。

枚举左半边 $1$ 至 $mid$ 所获得的钻石数 $k$ 和钱数 $c$，然后考虑求出右边 $mid+1$ 至 $n$ 的所有方案中，钻石数为 $i-k$，钱数为 $\left [ f_{i,j}-c,f_{i,j+1}-c \right ) $ 的概率之和，乘以左半边的概率即可。

右半边的查找可以把所有方案按照「钻石数」为第一关键字，「钱数」为第二关键字排序，预处理概率的前缀和，再用 lower_bound 来查找。

复杂度 $O(nm^2+2^{mid}+2^{n-mid}+2^{n-mid}log_22^{n-mid}+nm2^{mid}\log_2(2^{n-mid}))$，注意到 $2^{n-mid}$ 是在 $log$ 里的，所以在不炸空间的情况下可以尽可能的将 $mid$ 变小。

代码（又慢又长）：

 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
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=33;
int n,m,v[N],p[N],c[N],d[N];
int f[N][N][N];
void DP(){
    memset(f,63,sizeof(f));
    for(int i=0;i<=n;i++) f[0][i][0]=0;
    for(int i=1;i<=m;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=i;k++){
                f[i][j][k]=f[i-1][j][k];
                if(k>=1&&j>=d[i]){
                    f[i][j][k]=min(f[i][j][k],f[i-1][j-d[i]][k-1]+c[i]);
                }
            }
}
struct node{int d,c;double p;}lg[1<<21],rg[1<<21];
bool cmp(node x,node y){return (x.d==y.d)?x.c<y.c:x.d<y.d;}
int cl,cr;
double sr[1<<21];
void dfs(int d,int ed,int nwd,int nwc,double p,node (&s)[1<<21],int &cc){
    if(d>ed){
        if(p!=0) s[++cc]={nwd,nwc,p};
        return;
    }
    dfs(d+1,ed,nwd,nwc+v[d],p*(::p[d]/100.0),s,cc);
    dfs(d+1,ed,nwd+1,nwc,p*(1-::p[d]/100.0),s,cc);
}
double ask(int d,int l,int r){
    int pl=lower_bound(rg+1,rg+cr+1,(node){d,l,0},cmp)-rg;
    int pr=lower_bound(rg+1,rg+cr+1,(node){d,r,0},cmp)-rg;
    return sr[pr-1]-sr[pl-1];
}
void work(){
    cl=cr=0;
    cin>>n>>m;int mid=min(n/2,10);
    for(int i=1;i<=n;i++) cin>>v[i]>>p[i];
    for(int i=1;i<=m;i++) cin>>c[i]>>d[i];
    DP(),dfs(1,mid,0,0,1,lg,cl),dfs(mid+1,n,0,0,1,rg,cr);
    sort(rg+1,rg+cr+1,cmp);
    for(int i=1;i<=cr;i++) sr[i]=sr[i-1]+rg[i].p;
    double ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            int l=f[m][i][j],r=f[m][i][j+1];
            double sum=0;
            for(int k=1;k<=cl;k++)
                sum+=ask(i-lg[k].d,l-lg[k].c,r-lg[k].c)*lg[k].p;
            ans+=sum*j;
        }
    }
    printf("%.4lf\n",ans);
}
int main(){
    int t;cin>>t;
    while(t--) work();
    return 0;
}