【Luogu1291】百事世界杯之旅(动态规划,数学期望)
规划 动态 之旅 数学 期望 世界杯
2023-09-11 14:14:41 时间
【Luogu1291】百事世界杯之旅(动态规划,数学期望)
题面
题解
设\(f[i]\)表示已经集齐了\(i\)个名字的期望
现在有两种方法:
先说我自己的:
\[f[i]=f[i-1]+1+(1-p)(1*p^1+2*p^2+....)
\]
其中\(p=\frac{i-1}{n}\)
为什么,很简单
首先要多收集一个,期望\(+1\)是显然的
但是还可能一直买到了已经有的名字中的一个
有\(p\)的概率多买一个
\(p^2\)的概率多买两个
这样无穷的算下去
然后对于后面那个式子
做两次错位相减(其实就是一个无穷级数)
推出
\[f[i]=f[i-1]+1+\frac{i-1}{n-(i-1)}
\]
然后递推就行了
第二种方法:
\(fdf\)的方法(感觉这种方法也很强呀)
设\(f[i]\)表示已经收集了\(i\)个
收集到\(n\)个需要的期望
\[f[i]=\frac{i}{n}(f[i]+1)+\frac{n-i}{n}(f[i+1]+1)
\]
\[\frac{n-i}{n}f[i]=\frac{n-i}{n}f[i+1]+1
\]
\[f[i]=f[i+1]+\frac{n}{n-i}
\]
初值:\(f[n]=0\)
倒着算即可
贴上我自己的代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
int n;
int ws(ll x)
{
int ret=0;
while(x)++ret,x/=10;
return ret;
}
struct Num
{
ll a,b;
void easy()
{
ll d=__gcd(a,b);
a/=d;b/=d;
}
void output()
{
easy();
if(b==1){printf("%lld\n",a);return;}
ll k=a/b;a-=k*b;
int blk=ws(k),ss=max(ws(a),ws(b));
for(int i=1;i<=blk;++i)putchar(' ');
printf("%lld\n",a);
printf("%lld",k);
for(int i=1;i<=ss;++i)putchar('-');putchar('\n');
for(int i=1;i<=blk;++i)putchar(' ');
printf("%lld\n",b);
}
}f[50];
Num operator+(Num a,Num b)
{
ll d=a.b/__gcd(a.b,b.b)*b.b;
return (Num){a.a*(d/a.b)+b.a*(d/b.b),d};
}
Num operator*(Num a,Num b)
{
Num c=(Num){a.a*b.a,a.b*b.b};
c.easy();
return c;
}
int main()
{
n=read();
f[0]=(Num){0,1};
for(int i=1;i<=n;++i)
{
f[i]=f[i-1]+(Num){1,1};
f[i]=f[i]+(Num){i-1,n-i+1};
}
f[n].output();
return 0;
}
相关文章
- 本人博客园 重新规划和分类(有待改进)
- Java实现 LeetCode 629 K个逆序对数组(动态规划+数学)
- Java实现 LeetCode 629 K个逆序对数组(动态规划+数学)
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- HDU 1087 Super Jumping! Jumping! Jumping!(动态规划)
- linux学习规划
- LeetCode-面试题 17.09. 第 k 个数【三指针,动态规划,最小堆】
- Leetcode学习计划之动态规划入门day5(53,918)
- 【【henuacm2016级暑期训练】动态规划专题 J】Red-Green Towers
- 精品数学规划求解器:Gurobi Optimizer 10.0.1 Crack
- Algorithm:C++语言实现之动态规划算法相关(矩阵连乘状态转移方程、字符串的交替连接、分析格网棋盘的特点、最短路线问题、生产计划问题、动态规划解下列非线性规划)
- 【路径规划】基于D*算法的移动机器人路径规划(Matlab代码实现)
- 2320. 统计放置房子的方式数-动态规划
- 剑指 Offer II 104. 排列的数目-动态规划算法
- 714. 买卖股票的最佳时机含手续费-动态规划算法
- 1043. 分隔数组以得到最大和-动态规划算法
- 915. 分割数组-动态规划算法
- 1340. 跳跃游戏 V-动态规划加dfs
- 动态规划典型例题--连续子数组的最大和
- POJ 2151 Check the difficulty of problems (动态规划-可能DP)
- 动态规划0—1背包问题
- java专业规划(转载)
- leetcode算法之动态规划总结(11种DP类型,70道全部搞懂)——总结非常全面
- 动态规划算法模板和demo
- 动态规划 滚动数组减少 空间复杂度
- 动态规划_C#
- 基于模型预测(MPC)的四轮转向车辆轨迹规划(Matlab代码实现)
- 【运维规划、管理、体系建设】饿了么运维基础设施进化史之精细化运维和数据化运营
- 【强化学习】读书手札:动态规划(DP)&蒙特卡洛(MC)&时序差分(TD)区别
- 动态规划03---你的背包怎么背也背不烂~~~专治各种完全背包问题