Buy(CC LEBOXES)

题目大意

给出n个袋子和m个粮食，每个袋子有p[i]%的概率获得v[i]个金币，有1-p[i]%的概率获得1个钻石，而购买一个粮食要付出c[i]个金币和d[i]个钻石。求购买粮食的期望个数。 n,m<=30 v[i],c[i]<=10^7,p[i]<=100

注意到n很小，也就是钻石数很小

设f[i][j]表示拥有钻石数为j时，购买i个粮食所需的最小金币代价，这是个经典背包问题，可以O(n^3)解决。 如果直接暴力所有袋子的状态来计算期望，复杂度是O(n*2^n)。

可以考虑折半搜索。

先暴力处理前a个袋子的状态。 dfs(i,v,z,p)表示当前取到第i个(第i个袋子的状态还未知)，当前有v个金币和z个钻石，此时的概率为p。 那么当i>a时，我们就退出dfs，并把dfs(a+1,v,z,p)的状态保存下来，t[z]表示拥有z个钻石的状态的个数，a[z][j].v表示拥有z个钻石的状态中第j个状态的金币数，a[z][j].p表示拥有z个钻石的状态中第j个状态的概率值，这样我们就把前a个袋子的状态都保存下来了。 然后对于所有的a[i]以a[i][j].v为关键字从小到大排序，排序后再处理a[i][j].s表示a[i][1~j].p的和。 dfs的复杂度为(2^a),排序的复杂度为O(2a*2^a) 然后再dfs一次处理剩余袋子的状态。 设结束状态为(v,z,p)(意义相同),计算贡献： 枚举购买的粮食数i，枚举前a个袋子获得的钻石数记作z1，前a个袋子获得的金币数记作v1，当然v1时不能枚举的，因为 f[i][z+z1]<=v+v1<f[i+1][z+z1] ,所以可以二分出v1在a[z1]的位置范围l~r，总概率就等于p*(a[z1][r].s-a[z1][l-1].s)，期望贡献为总概率*i。 设b=n-a，后半部分的复杂度为O(m*a^2*2^b)（这里把二分的复杂度估计为a，即所有t[z1]=2^a,实际达不到） 当a=2n/3时复杂度为O( 4n3∗22n3+m∗4n29∗2n3 )这个复杂度已经可以通过所有测试数据了。

代码

#include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #define fo(i,a,b) for(i=a;i<=b;i++) #define fod(i,a,b) for(i=a;i>=b;i--) using namespace std; const int maxn=30+5;const int ma=1048576; int i,j,n,t,m,l,n1,n2; int f[maxn][maxn],v[maxn],p[maxn],c[maxn],d[maxn]; int z[maxn]; struct ar{ int x;double p,sum; } a[21][ma]; double ans; void dfs(int x,int y,int y1,double s){ if (x>n1){ a[y1][++z[y1]].x=y,a[y1][z[y1]].p=s; return; }double s1=(double)p[x]/100; dfs(x+1,y+v[x],y1,s*s1),dfs(x+1,y,y1+1,s*(1-s1)); } int fen(int t,int x){ int l=1,r=z[t]; if (a[t][r].x<x) return r+1; while (l<r){ int m=(l+r)/2; if (a[t][m].x>=x) r=m;else l=m+1; }return l; } void df(int x,int y,int y1,double s){ if (x>n){ int t,i; fo(t,0,n1){ fo(i,1,m) if (f[i][t+y1]<f[m+1][0]){ int d=t+y1; int s1=f[i][d]-y,s2=f[i+1][d]-y;if (s2<=0) continue; int l=fen(t,s1),r=fen(t,s2);r--; ans+=(double)i*s*(a[t][r].sum-a[t][l-1].sum); }else break; } return; }double s1=(double)p[x]/100; df(x+1,y+v[x],y1,s*s1),df(x+1,y,y1+1,s*(1-s1)); } bool cmp(ar x,ar y){ return x.x<y.x; } int main(){ scanf("%d",&t); while(t){ t--; scanf("%d%d",&n,&m); fo(i,1,n) scanf("%d%d",&v[i],&p[i]); fo(i,1,m) scanf("%d%d",&c[i],&d[i]); memset(f,127/2,sizeof(f)); fo(i,0,n) f[0][i]=0; fo(i,1,m) fod(j,m,1) fo(l,d[i],n) f[j][l]=min(f[j][l],f[j-1][l-d[i]]+c[i]); ans=0; n1=n/3*2; memset(z,0,sizeof(z)); dfs(1,0,0,1); fo(i,0,n1) { sort(a[i]+1,a[i]+1+z[i],cmp); fo(j,1,z[i]) a[i][j].sum=a[i][j-1].sum+a[i][j].p; } df(n1+1,0,0,1); printf("%.4lf\n",ans); } }