海南行指网站开发公司,wordpress文章阅读数,网站在百度搜索不到,无线网络设计实验报告正题
题目链接:https://www.luogu.com.cn/problem/CF1267G 题目大意
给出nnn个物品#xff0c;你可以进行如下操作
花费xxx获得随机一个物品。花费cic_ici获得第iii个物品。 1≤n≤100,1≤x≤10000,∑ai≤1041\leq n\leq 100,1\leq x\leq 10000,\sum a_i\leq 10^41≤n≤1…正题
题目链接:https://www.luogu.com.cn/problem/CF1267G 题目大意
给出nnn个物品你可以进行如下操作
花费xxx获得随机一个物品。花费cic_ici获得第iii个物品。
1≤n≤100,1≤x≤10000,∑ai≤1041\leq n\leq 100,1\leq x\leq 10000,\sum a_i\leq 10^41≤n≤100,1≤x≤10000,∑ai≤104 解题思路
一个显然的策略是我们先roll完再买所以我们可以分开考虑两部分先。
首先假设我们roll到了xxx个物品显然所有大小为xxx的物品集合都是等概率出现的。而至于roll出xxx个物品的期望花费我们也很好算。
但是我们显然很难从一种情况下的下一步方案考虑因为能到达每个方案的期望都是不同的而我们不可能记录所有方案。
但是有一个很巧妙的方法我们花钱也可以视为随意rollrollroll物品假设目前没有获得的物品费用和为sss个数为kkk那么我们就可以视为花费sk\frac{s}{k}ks的期望随机rollrollroll出一个物品。
此时两种方案造成的结果都是多一个随机未获得物品但是花费不同我们直接取minminmin即可。
那么现在的做法已经很显然了设fi,jf_{i,j}fi,j表示iii个物品的集合中花费和为jjj的概率然后考虑两种方案的哪个更优就好了。
时间复杂度O(n∑ai)O(n\sum a_i)O(n∑ai) code
#includecstdio
#includecstring
#includealgorithm
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 i1,a;in;i){scanf(%d,a);suma;for(int ji;j1;j--)for(int ksum;ka;k--)f[j][k]f[j-1][k-a]*j/double(n-j1);}for(int i1;in;i)for(int j0;jsum;j)if(f[i][j]!0.0)ans(ansf[i][j]*min(((double)n/i1.0)*x,(double)j/i));printf(%.12lf\n,ans);return 0;
}
