Codechef LEBOXES

原题链接

CC LEBOXES

题目大意

一共有 n 个袋子和m个粮食。 每个粮食需要支付 Ci 的金钱和 Di 的钻石购买。 每个袋子有 Pi 的概率装有 Vi 的金币，有 1−pi 的概率装有1个钻石。 问每个袋子都打开的情况下，期望拿到多少个粮食。

n,m≤30;Vi,Ci≤107

解题思路

meet in the middle

将盒子分为前后两个部分.对于每部分，我们暴力枚举状态 (V,D,P) 表示获得 V 的金钱,D个钻石，概率为 P ,将状态按D的值分类。

对于每个部分，将 D 值相同的按金钱数排序，并维护前缀概率和。

dp，fi,j表示在拥有 i 个钻石的情况下，获得j个粮食的最小花费金钱数，这个其实就是一个简单的背包问题。

最后，我们需要，将前后两个部分合并，枚举 i,j,k ,表示前半部分获得 i 个钻石，后半部分获得j个钻石，最终获得 k 个粮食，求当前概率。

易得需要钱数≥fi+j,k,然后我们就是在排序后的状态使用两个指针扫描即可。

参考代码

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define maxn 35 #define maxp 50005 #define db double #define ld long double #define pild pair<int,ld> #define fi first #define se second #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define min(a,b) (((a) < (b)) ? a : b) using namespace std; int T,n,m,mid; int f[maxn][maxn],c[maxn],d[maxn]; db p[maxn],ans; int v[maxn]; int tot[2][maxn]; pild st[2][maxn][maxp]; void dfs(int w,int to,int money,int dio,ld pp){ if (w==to) { if (w==mid+1) { tot[0][dio]++; int tmp=tot[0][dio]; st[0][dio][tmp]=mp(money,pp); } else { tot[1][dio]++; int tmp=tot[1][dio]; st[1][dio][tmp]=mp(money,pp); } return; } dfs(w+1,to,money,dio+1,pp*(1-p[w])); dfs(w+1,to,money+v[w],dio,pp*p[w]); } int main(){ scanf("%d",&T); while (T--) { mem(tot,0); mem(f,63); mem(c,0); mem(d,0); ans=0; scanf("%d%d",&n,&m); fo(i,1,n) { scanf("%d%lf",&v[i],&p[i]); p[i] /= 100; } fo(i,1,m) scanf("%d%d",&c[i],&d[i]); f[0][0]=0; fo(i,1,m) fd(j,i,1) fo(k,0,n-d[i]) f[j][k+d[i]]=min(f[j][k+d[i]],f[j-1][k]+c[i]); fo(i,1,m) fo(j,1,n) f[i][j]=min(f[i][j],f[i][j-1]); mid=n / 2; dfs(1,mid+1,0,0,1); dfs(mid+1,n+1,0,0,1); fo(i,1,mid) { sort(st[0][i]+1,st[0][i]+tot[0][i]+1); st[0][i][tot[0][i]+1].se=0; fd(j,tot[0][i],0) st[0][i][j].se+=st[0][i][j+1].se; } fo(i,1,n-mid) { sort(st[1][i]+1,st[1][i]+tot[1][i]+1); st[1][i][tot[1][i]+1].se=0; fd(j,tot[1][i],0) st[1][i][j].se+=st[1][i][j+1].se; } fo(i,0,mid) { if (tot[0][i]==0) continue; fo(j,0,n-mid) { if (tot[1][j]==0) continue; fo(k,1,m) { if (f[k][i+j]>1e9) continue; int money=f[k][i+j]; int w=tot[0][i]; fo(l,1,tot[1][j]) { while (w && st[0][i][w].fi+st[1][j][l].fi>=money) w--; ans+=(st[1][j][l].se-st[1][j][l+1].se)*st[0][i][w+1].se; } } } } printf("%.4lf\n",ans); } return 0; }