CF1267G-Game Relics【数学期望,dp】
2022/1/24 23:08:28
本文主要是介绍CF1267G-Game Relics【数学期望,dp】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
正题
题目链接:https://www.luogu.com.cn/problem/CF1267G
题目大意
给出\(n\)个物品,你可以进行如下操作
- 花费\(x\)获得随机一个物品。
- 花费\(c_i\)获得第\(i\)个物品。
\(1\leq n\leq 100,1\leq x\leq 10000,\sum a_i\leq 10^4\)
解题思路
一个显然的策略是我们先roll完再买,所以我们可以分开考虑两部分先。
首先假设我们roll到了\(x\)个物品,显然所有大小为\(x\)的物品集合都是等概率出现的。而至于roll出\(x\)个物品的期望花费我们也很好算。
但是我们显然很难从一种情况下的下一步方案考虑,因为能到达每个方案的期望都是不同的,而我们不可能记录所有方案。
但是有一个很巧妙的方法,我们花钱也可以视为随意\(roll\)物品,假设目前没有获得的物品费用和为\(s\),个数为\(k\),那么我们就可以视为花费\(\frac{s}{k}\)的期望随机\(roll\)出一个物品。
此时两种方案造成的结果都是多一个随机未获得物品,但是花费不同,我们直接取\(min\)即可。
那么现在的做法已经很显然了,设\(f_{i,j}\)表示\(i\)个物品的集合中花费和为\(j\)的概率,然后考虑两种方案的哪个更优就好了。
时间复杂度:\(O(n\sum a_i)\)
code
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,sum; double ans,x,f[110][110000]; int main() { scanf("%d%lf",&n,&x);x/=2.0; f[0][0]=1; for(int i=1,a;i<=n;i++){ scanf("%d",&a);sum+=a; for(int j=i;j>=1;j--) for(int k=sum;k>=a;k--) f[j][k]+=f[j-1][k-a]*j/double(n-j+1); } for(int i=1;i<=n;i++) for(int j=0;j<=sum;j++) if(f[i][j]!=0.0) ans=(ans+f[i][j]*min(((double)n/i+1.0)*x,(double)j/i)); printf("%.12lf\n",ans); return 0; }
这篇关于CF1267G-Game Relics【数学期望,dp】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享