SGU - 495 概率DP
2024-10-22 04:49:24
题意:n个带礼物的盒子和m个人,每个人拿一个盒子并放回,如果里面有礼物就拿走(盒子还是留下),问m个人带走礼物的期望
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int oo = 0x3f3f3f3f;
const double eps = 1e-7;
typedef long long ll;
ll read(){
ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
double dp[maxn];
int n,m;
int main(){
while(cin>>n>>m){
dp[1]=1;//n件任拿一件
rep(i,2,m){
dp[i]=(dp[i-1]+1)*(n-dp[i-1])/n+dp[i-1]*dp[i-1]/n;
}
printf("%.9lf\n",dp[m]);
}
return 0;
}
或者
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e6+11;
const int oo = 0x3f3f3f3f;
const double eps = 1e-7;
typedef long long ll;
ll read(){
ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
double dp[maxn];
int n,m;
int main(){
while(cin>>n>>m){
dp[1]=1;//n件任拿一件
rep(i,2,m){
dp[i]=dp[i-1]+(double)(n-dp[i-1])/n;
}
printf("%.9lf\n",dp[m]);
}
return 0;
}
最新文章
- .NET面试题系列[10] - IEnumerable的派生类
- 手把手教你写Sublime中的Snippet
- mysql数据库的基本操作
- Java 7 Concurrency Cookbook 翻译 第一章 线程管理之四
- ssh免密码登陆设置
- zip生成
- Silverlight的ComboBox 的绑定和取值
- hdu 1398 Square Coins(生成函数,完全背包)
- jQ的一些常识
- 配置安装nginx
- python中socket、进程、线程、协程、池的创建方式和应用场景
- Windows Internals 笔记——CreateProcess
- 傻瓜学编程之block_1
- css根据子元素多少类设置子元素的属性--九宫格
- re正则匹配使用
- 【北京】安全研究员/工程师-20-35K,人体工程学座椅坐等你来~
- 实习小结(四)--- MyBatis Generator使用
- 获得当前正在显示的activity的类名
- [LOJ500]ZQC的拼图
- 附录A培训实习生-面向对象基础构造方法和带参数的构造方法(2)