admin 管理员组文章数量: 887021
爱奇艺
题目描述：
/**
牛牛和羊羊非常无聊.他们有n + m个共同朋友,他们中有n个是无聊的,m个是不无聊的。
每个小时牛牛和羊羊随机选择两个不同的朋友A和B.
(如果存在多种可能的pair(A, B),任意一个被选到的概率相同。),
然后牛牛会和朋友A进行交谈,羊羊会和朋友B进行交谈。
在交谈之后,如果被选择的朋友之前不是无聊会变得无聊。
现在你需要计算让所有朋友变得无聊所需要的时间的期望值。输入描述:
输入包括两个整数n 和 m(1 ≤ n, m ≤ 50)输出描述:
输出一个实数,表示需要时间的期望值,四舍五入保留一位小数。输入例子1:
2 1输出例子1:
1.5
*/ 思路如下：
概率题（采用记忆化搜索策略 O(m*n)）
F(n,m)表示n个无聊，m个有聊变为全部无聊期望时间
状态(n, m)的下一个状态可能是 (n, m) (n+1, m-1) (n+2, m-2)分别对应概率为p1, p2, p3
F(n, m)=p1*(F(n, m)+1)+p2*(F(n+1, m-1)+1)+p3*(F(n+2, m-2)+1)
total=m+n
p1=(n C 2)/(total C 2)
p2=(n C 1)*(m C 1)/(total C 2)
p3=(m C 2)/(total C 2)
p1+p2+p3=1
简化公式
(1-p1)*F(n, m)=1+p2*F(n+1, m-1)+p3*F(n+2, m-2)
由于此种情况n>=1 m>=1 p1肯定不为0
p1=n*(n-1)/((n+m)*(n+m-1))
p2=2*m*n/((n+m)*(n+m-1))
p3=m*(m-1)/((n+m)*(n+m-1))
base case:
F(n,0)=0
F(n, 负数)=0
代码如下：
#include<stdio.h>
#include<iostream>#define MAX 101using namespace std;//标记备忘录是否有效
bool marked[MAX][MAX];
//行为n 列为m memo只记录n>=1 m>=1的情况
double memo[MAX][MAX];//n在第一次进入就确保>=1,且n只会增加
//m在第一次进入确保>=1,m会减少
double DFS(int n, int m){if(m<=0)return 0;if(marked[n][m]){return memo[n][m];}double p1, p2, p3;p1=1.0*n*(n-1)/((n+m)*(n+m-1));p2=1.0*2*m*n/((n+m)*(n+m-1));p3=1.0*m*(m-1)/((n+m)*(n+m-1));memo[n][m]=1.0*(1+p2*DFS(n+1, m-1)+p3*DFS(n+2, m-2))/(1-p1);marked[n][m]=true;return memo[n][m];
}int RoundDouble(double number)
{return (number > 0.0) ? (number + 0.5) : (number - 0.5);
}int main()
{
// double a=3.64;
// int aInt=RoundDouble(a*10);
// a=aInt/10.0;
// printf("%.1lf\n", a);int n, m;scanf("%d%d", &n, &m);if(n<=0 || m<=0)return -1;double res=DFS(n, m);int resInt=RoundDouble(res*10);res=resInt/10.0;printf("%.1lf", res);return 0;
}
本文标签： 爱奇艺
版权声明：本文标题：爱奇艺 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1688066092h175139.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论