7.16 T1 礼物

题目大意：n个物品，每次有pi的概率买到，可以重复买，也可以什么都没买到，但算一次购买，问把所有东西都买到的期望次数。对于10%的数据，N = 1;对于30%的数据，N ≤ 5;对于100%的数据，N ≤ 20 ，0 < Wi ≤ 10^9 ，0 < Pi ≤ 1且∑Pi ≤ 1

刚看到这道题，我去，概率与期望，心凉了一半（太菜了。。）放到了最后做。

n很小，所以考虑状压，f[i]表示当前n种物品的状态为i的期望购买次数，0表示买了，1表示没买（我正好跟别人反着QAQ），根据以往期望题的惯例，考虑倒着转移，所以f[i]就是状态为i，到全买到的期望购买次数。f[0]表示全买了，到全买的期望是0，f[1<<n+1)-1]表示都没买，即最终答案。

转移方程就是f[i]=Σ(f[j]+1)*p[k]+(1-Σp[k])*（f[i]+1）   j比i多一个0就是多买到一种，k就是那种物品

意思就是从f[j]转移的期望与这次购买什么都没买到或买到了重的的期望，Σp[k]表示买到新物品的概率，1-Σp[k]就是买旧的或不买，这是状态不会改变，从f[i]转移过来。

两边都有f[i]，高斯消元？假的，移一下项就得到了f[i]=Σf[j]*p[k]/Σp[k].

考试的时候推式子没有考虑买一样的东西，期望题真是弱爆了，而且n==1那个点也没想到要输出1/p[1]  谁知道想啥呢，而且考试时一个题思路不是很清晰而且样例一直过不去，做了1小时以上了，就先把它放一放，努力拿最高分。

#include<iostream> #include<cstdio> #define ll long long using namespace std; int n,b[(1<<21)+15]; ll w[25],ans; double p[25],pp,pi,f[(1<<21)+15]; int lowbit(int x) {return x&(-x); } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf%lld",&p[i],&w[i]);if(p[i]>0) ans+=w[i];}printf("%lld\n",ans);for(int i=0;i<=n;i++){b[1<<i]=i;}for(int i=0;i<=(1<<n+1)-1;i++){double h=0;for(int j=i;j;j-=lowbit(j)){int tmp=lowbit(j);f[i]+=f[i-tmp]*p[b[tmp]];h+=p[b[tmp]];}if(h) f[i]=(f[i]+1)/h;}printf("%.3lf\n",f[(1<<n+1)-1]);return 0; } 别颓

 

转载于:https://www.cnblogs.com/jrf123/p/11198805.html

总结

以上是生活随笔为你收集整理的7.16 T1 礼物的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。