JZOJ4703 Buy

题目大意

有n个袋子，每个袋子i有p[i]概率获得a[i]的钱，(1-p[i])获得1个钻石。 有m个物品，获取物品i需要c[i]的钱，和d[i]的钻石。 求获得物品的期望。 n,m≤30。 a[i],p[i],c[i]≤ 107

分析

考虑 O(2n) 暴力 很明显袋子只有两种取法。我们暴力出一种方案，设此时金钱数为V，钻石为T，概率为P，那么对答案的贡献就是P*可以获得的最多物品cnt。 现在暴力的主要问题是如何知道cnt。我们设f[i][j]表示有i个钻石，获得j个物品要花的最少钱数。很明显可以背包乱搞。到时候我们就知道cnt是多少了—— cnt=x|f[T][x]<=v

代码

#include<cstdio> #include<algorithm> using namespace std; #define fo(i,j,k) for(i=j;i<=k;i++) #define fd(i,j,k) for(i=j;i>=k;i--) const int mx=1000000007; struct rec { int v; double p; }b[31][1048576+1];//0也有用 int a[40],c[40],d[40],f[35][35],i,T,lb,rb,l,r,lf,rf,stp,j,k,n,m,mid,T1; double p[40],ans; bool cmp(rec a,rec b) { return a.v<b.v; } void dfs(int t,int v,double P,int x) { if (x>stp) { b[t][0].v++; b[t][b[t][0].v].v=v; b[t][b[t][0].v].p=P; return; } dfs(t,v+a[x],P*p[x],x+1); dfs(t+1,v,P*(1-p[x]),x+1); } void df(int t,int v,double P,int x) { if (x==stp) { fo(T,0,stp) fo(i,1,m) { lf=f[t+T][i]-v; rf=f[t+T][i+1]-v; l=1; r=b[T][0].v; while (l<r) { mid=(l+r)/2; if (b[T][mid].v>=lf) r=mid; else l=mid+1; } lb=l; r=b[T][0].v; while (l<r) { mid=(l+r+1)/2; if (b[T][mid].v<rf) l=mid; else r=mid-1; } rb=l; if (b[T][lb].v<lf) continue; if (b[T][rb].v>=rf) continue; ans=ans+double(i)*P*(b[T][rb].p-b[T][lb-1].p); } return; } df(t,v+a[x],P*p[x],x-1); df(t+1,v,P*(1-p[x]),x-1); } int main() { scanf("%d",&T1); while (T1--) { scanf("%d %d",&n,&m); ans=0.0; fo(i,1,n) { scanf("%d %lf",a+i,p+i); p[i]=p[i]/100.0; } fo(i,1,m) scanf("%d%d",c+i,d+i); fo(i,0,30) fo(j,0,30) f[i][j]=mx; f[0][0]=0; for (i=1;i<=m;i++) for (j=n;j>=d[i];j--) for (k=i;k;k--) f[j][k]=min(f[j][k],f[j-d[i]][k-1]+c[i]); for (i=1;i<=n;i++) for (j=1;j<=m;j++) f[i][j]=min(f[i][j],f[i-1][j]); stp=n/3*2; dfs(0,0,1.0,1); fo(i,0,stp) { sort(b[i]+1,b[i]+1+b[i][0].v,cmp); fo(j,2,b[i][0].v) b[i][j].p+=b[i][j-1].p; } df(0,0,1.0,n); printf("%.4lf\n",ans); fo(i,0,stp) b[i][0].v=0; } }

不足

1，写个01背包都能错——一个物品多次重复计算； 2，二分时的continue没有涵盖所有条件，当lb>rb的时候没有考虑。 3，背包忘记f[i][j]可以等于f[i-1][j]；