概率 · dp练习 (16.04.16)

概率 · dp练习 (16.04.16)

由于前辈出的三道题中有一道是自己以前写过的，且写过博文，所以本文就再找了一道和概率相关的简单题来凑数。

UVA - 12230 Crossing Rivers

​​ 大意：一人从西岸走到东岸，之间有许多条河，人在陆地上的行走速度是1。河的参数：p,l,v 分别表示河的西岸距离起点陆地的距离，河的宽度，船儿在河里的行驶速度。 分析：船儿在河里的行驶极端状况： （1） |        | | —> | |        | （2） | —> | | <— | | —-> | 所以平均的行驶时间是 2l/v 结果就是： ∑2livi+D−∑li

#include #include using namespace std;int main(){ int n,d; int ca=0; while(~scanf("%d%d",&n,&d)){ if(n==0 && d==0) break; double ans=0; int p,l,v; for(int i=0;i

hdu 4405 Aeroplane chess

​​ 大意：有N+1个格子，从0开始，每一次执色子，1—6个点数，向前跳跃，直到>=n点，其中还有飞跃点对ai,bi，表示从ai能直接到bi，求解掷色子的个数的期望。 分析：for k=1–>6 : dp[i]=∑(dp[i+k]×16)+1 模拟跳跃，即程序中的continue。

#include #include #include #include #include using namespace std;const int N=1e3+10,M=2e5+20;struct node{ int s,e;}f[N];double dp[M];int main(){ //freopen("cin.txt","r",stdin); int n,m; while(cin>>n>>m){ if(n==0&&m==0) break; memset(dp,0,sizeof(dp)); for(int i=0;i=0;i--){ bool tag=0; for(int j=0;j

hdu 5001 walk

​​ 大意：对于一幅无向图，从任意一个点出发走k步后求解不经过i结点的概率。 分析：设dp[i][j]的意义是经过i步后到达j的概率，那么针对vector的前向星暴力求解即可。 参照网上代码修改AC后的疑惑： 我觉得这题很奇葩，如果它是问最后第d步没包含i点的话，最开始为什么一定要跳过i点？如果它是问每一步均不包含i点，那么为什么最后求解d步到达其他点的概率就是答案？ —————————————————— 16.04.25更新： 有些点经过d步不会经过它。

//bad code: for(int i=1;i<=n;i++){ memset(dp,0,sizeof(dp)); for(int j=1;j<=n;j++) dp[0][j]=1.0/n; for(int j=1;j<=d;j++){ for(int k=1;k<=n;k++){ if(k==i) continue; int len=edge[k].size(); for(int h=0;h

对比：

//AC: for(int i=1;i<=n;i++){ memset(dp,0,sizeof(dp)); for(int j=1;j<=n;j++) dp[0][j]=1.0/n; for(int j=1;j<=d;j++){ for(int k=1;k<=n;k++){ if(k==i) continue; int len=edge[k].size(); for(int h=0;h

完整代码：

#include #include #include #include #include using namespace std;double dp[10005][55];int main(){ //freopen("cin.txt","r",stdin); int t; cin>>t; while(t--){ int n,m,d; scanf("%d%d%d",&n,&m,&d); vector edge[55]; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。